#include <iostream>
#include <fstream>

using namespace std;

void inmultire (int a[2][2])
{
      int i,j,k;
      int c[2][2]={0};
               for (i = 0 ; i < 2; i++)
                   for ( j = 0 ; j< 2; j++)
                       for ( k = 0; k <2 ;k++)
                       c[i][j] = (c[i][j] +1LL* a[i][k]* a[k][j]) % 666013;
                for (i = 0 ; i < 2; i++)
                   for ( j = 0 ; j< 2; j++)
                   a[i][j] = c[i][j];        
 }

void putere( int ma[2][2],int a,int b, int c,int d,long  p  )
{
     if ( p == 1 ) 
         return;
     else if ( p % 2 == 0 ) 
          {
              inmultire(ma);
              putere(ma,a,b,c,d,p/2);
          }
          else 
          {
            a = ma[0][0];
            b = ma[0][1];
            c = ma[1][0];
            d = ma[1][1];
            inmultire (ma);
            putere(ma,a,b,c,d, (p-1)/2);
            int mc[2][2]={0};
            int i,j;
            mc[0][0] = (1LL*a * ma[0][0] + 1LL*b * ma[1][0]) % 666013;
            mc[0][1] = (1LL*a* ma[0][1] + 1LL*b * ma[1][1]) % 666013;
            mc[1][0] = (1LL*c * ma[0][0] + 1LL*d* ma[1][0]) % 666013;
            mc[1][1] = (1LL*c* ma[0][1] + 1LL*d* ma[1][1]) % 666013;
              
             for (i = 0 ; i < 2; i++)
                   for ( j = 0 ; j< 2; j++)
                   ma[i][j] = mc[i][j];         
           }
}

int main()
{

    ifstream in("kfib.in");
    ofstream out("kfib.out");
    long k;
    in>>k;
    int a,b,c,d;
    int matrix[2][2];
    matrix[0][0] = a= 1;
    matrix[0][1] = b= 1;
    matrix[1][0] = c= 1;
    matrix[1][1] = d= 0;
    putere(matrix,a,b,c,d,k-1);
    out<<matrix[0][0] ;
    in.close();
    out.close();
    return 0;
}