#include <bits/stdc++.h>

using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

const int MOD = 666013;
struct mat{
    int mat[2][2];
};

const mat nll = {
     {{1,0},
     {0,1}}
};

const mat init = {
     {{0,1},
     {1,1}}


};

mat prod(mat a, mat b)
{
    mat rez;
    rez.mat[0][0] = (1LL*a.mat[0][0]*b.mat[0][0] + 1LL*a.mat[0][1]*b.mat[1][0])%MOD;
    rez.mat[0][1] = (1LL*a.mat[0][0]*b.mat[0][1] + 1LL*a.mat[0][1]*b.mat[1][1])%MOD;
    rez.mat[1][0] = (1LL*a.mat[1][0]*b.mat[0][0] + 1LL*a.mat[1][1]*b.mat[1][0])%MOD;
    rez.mat[1][1] = (1LL*a.mat[1][0]*b.mat[0][1] + 1LL*a.mat[1][1]*b.mat[1][1])%MOD;

    return rez;
}

mat pwr(mat a, int x)
{
    if(!x)
        return nll;
    if(x & 1)
            return prod(a,pwr(prod(a,a),x/2));
    return pwr(prod(a,a),x/2);
}




int main()
{
   int k;
   f>>k;
   g<<pwr(init,k).mat[0][1];


    return 0;
}