#include <bits/stdc++.h>

using namespace std;

ifstream F("kfib.in");
ofstream G("kfib.out");

int k;
const int MOD = 666013;
const int N = 2;

struct matrix {
  int m[N][N];
  matrix()
  {
     memset(m,0,sizeof(m));
  }
  matrix operator * (matrix b)
  {
     matrix c = matrix();
     for (int i = 0; i < N; ++i)
       for (int j = 0; j < N; ++j)
         for (int k = 0; k < N; ++k)
           c.m[i][j] = (c.m[i][j] + 1LL * m[i][k] * b.m[k][j]) % MOD;
     return c;
  }
} U, a, A;

matrix put( matrix x, int p )
{
    if( !p ) return U;
    if( p == 1 ) return x;
    matrix aux = put( x , p / 2 );
    aux = aux * aux ;
    if( p % 2 ) aux = aux * x;
    return aux;
}

int main()
{
    F >> k;
    U.m[ 0 ][ 0 ] = U.m[ 1 ][ 1 ] = 1;
    a.m[ 0 ][ 0 ] = 0;
    a.m[ 0 ][ 1 ] = a.m[ 1 ][ 0 ] = a.m[ 1 ][ 1 ] = 1;
    A = put( a , k );
    G << A.m[ 0 ][ 1 ];
    return 0;
}