#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 inm(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 n)
{
    if(!n)
        return nll;
    if(n & 1)
        return inm(a,pwr(inm(a,a),n/2));
    return pwr(inm(a,a),n/2);


}


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

    g<< pwr(init,k).mat[0][1];


    return 0;
}