#include <iostream>
#include <fstream>

using namespace std;
using LL = long long;
const int MOD = 666013;
const int SIZE_OF_FIB = 2;


LL f[SIZE_OF_FIB][SIZE_OF_FIB];
LL answer[SIZE_OF_FIB][SIZE_OF_FIB];
LL aux[SIZE_OF_FIB][SIZE_OF_FIB];

void prod ( LL input[SIZE_OF_FIB][SIZE_OF_FIB], LL matrix[SIZE_OF_FIB][SIZE_OF_FIB] ) {
    for ( int i = 0; i < SIZE_OF_FIB; i ++ )
       for ( int j = 0; j < SIZE_OF_FIB; j ++ )
          aux[i][j] = 0;
    for ( int i = 0; i < SIZE_OF_FIB; i ++ ) {
       for ( int j = 0; j < SIZE_OF_FIB; j ++ ) {
          for ( int k = 0 ; k < SIZE_OF_FIB; k ++ ) {
             aux[i][j] += input[i][k] * matrix[k][j];
             aux[i][j] %= MOD;
          }
       }
    }
    for ( int i = 0; i < SIZE_OF_FIB; i ++ )
       for ( int j = 0; j < SIZE_OF_FIB; j ++ )
          input[i][j] = aux[i][j];
}
void lgput_fib ( int e ) {
    while ( e > 0 ) {
       if ( e & 1 )
         prod ( answer, f );
       prod ( f, f ); e /= 2;
    }
}

void set_fib () {
    f[0][0] = 1; f[0][1] = 1;
    f[1][0] = 1; f[1][1] = 0;
    answer[0][0] = 1; answer[0][1] = 1;
    answer[1][0] = 1; answer[1][1] = 0;
}
ifstream fin ( "kfib.in" );
ofstream fout ( "kfib.out" );

int main()
{
   int k; fin >> k;
   set_fib ();
   lgput_fib ( k - 2 );

   if ( k == 0 )
     fout << 0;
   else
     fout << answer[0][0];
    return 0;
}