#include <fstream>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

typedef long long i64;

const int mod= 666013;

int z[2][2]= {{0, 1}, {1, 1}};
int d[2][2]= {{1, 1}, {1, 1}};

void lgput( int p ) {
    i64 aux00, aux01, aux10, aux11;
    for ( ; p>0; p/= 2 ) {
        if ( p%2==1 ) {
            aux00= ((i64)d[0][0]*z[0][0]+(i64)d[0][1]*z[1][0])%mod;
            aux01= ((i64)d[0][0]*z[0][1]+(i64)d[0][1]*z[1][1])%mod;
            aux10= ((i64)d[1][0]*z[0][0]+(i64)d[1][1]*z[1][0])%mod;
            aux11= ((i64)d[1][0]*z[0][1]+(i64)d[1][1]*z[1][1])%mod;
            d[0][0]= aux00, d[0][1]= aux01, d[1][0]= aux10, d[1][1]= aux11;
        }
        aux00= ((i64)z[0][0]*z[0][0]+(i64)z[0][1]*z[1][0])%mod;
        aux01= ((i64)z[0][0]*z[0][1]+(i64)z[0][1]*z[1][1])%mod;
        aux10= ((i64)z[1][0]*z[0][0]+(i64)z[1][1]*z[1][0])%mod;
        aux11= ((i64)z[1][0]*z[0][1]+(i64)z[1][1]*z[1][1])%mod;
        z[0][0]= aux00, z[0][1]= aux01, z[1][0]= aux10, z[1][1]= aux11;
    }
}

int main(  ) {
    int n;
    fin>>n;

    lgput(n-1);

    fout<<d[0][0]<<"\n";

    return 0;
}