#include <fstream>

using namespace std;

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

typedef long long i64;

const int mod= 666013;

int sol[1][2], a[2][2];

void lgput( int p ) {
    if ( p>0 ) {
        int aux[2][2];
        if ( p%2==1 ) {
            aux[0][0]= ((i64)sol[0][0]*a[0][0]+(i64)sol[0][1]*a[1][0])%mod;
            aux[0][1]= ((i64)sol[0][0]*a[0][1]+(i64)sol[0][1]*a[1][1])%mod;

            sol[0][0]= aux[0][0], sol[0][1]= aux[0][1];
        }

        aux[0][0]= aux[0][1]= aux[1][0]= aux[1][1]= 0;
        for ( int k= 0; k<=1; ++k ) {
            for ( int i= 0; i<=1; ++i ) {
                for ( int j= 0; j<=1; ++j ) {
                    aux[i][j]= ((i64)aux[i][j]+(i64)a[i][k]*a[k][j])%mod;
                }
            }
        }

        a[0][0]= aux[0][0], a[0][1]= aux[0][1], a[1][0]= aux[1][0], a[1][1]= aux[1][1];

        lgput(p/2);
    }
}

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

    a[0][1]= a[1][0]= a[1][1]= 1;
    sol[0][0]= 0, sol[0][1]= 1;
    lgput(k);

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

    return 0;
}