#include <fstream>

using namespace std;

const int mod = 666013;

long long a[2][2], ans[2][2];

void prod( long long a[2][2], long long b[2][2] ) {
    long long aux[2][2], b1[2][2];
    int i, j;
    for ( i = 0; i < 2; i ++ )
      for ( j = 0; j < 2; j ++ ) {
          aux[i][j] = a[i][j];
          b1[i][j] = b[i][j];
      }

    for ( i = 0; i < 2; i ++ )
      for ( j = 0; j < 2; j ++ )
        a[i][j] = ( aux[i][0] * b1[0][j] + aux[i][1] * b1[1][j] ) % mod;
}

int main()
{
    int k, i, j;
    ifstream fin ( "kfib.in" );
    ofstream fout ( "kfib.out" );
    fin >> k;
    ans[0][0] = 1;
    ans[1][1] = 1;
    a[0][0] = 1;
    a[0][1] = 1;
    a[1][0] = 1;

    if ( k == 0 )
      fout << 0;
    else {
        while ( k > 0 ) {
        if ( k % 2 == 1 )
          prod( ans, a );
        prod( a, a );
        k /= 2;


    }

    fout << ans[1][0];
    }



    fin.close();
    fout.close();

    return 0;
}