#include <fstream>
#define Int long long
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
const Int MOD=666013;
struct matr
{
    int a[2][2];
};
int k;
matr prod(matr,matr);
matr F,R;
int main()
{
    F.a[0][0]=F.a[1][0]=F.a[0][1]=1;
    R.a[0][0]=R.a[1][1]=1;
    f>>k;
    for(;k;k/=2)
    {
        if(k%2)
            R=prod(R,F);
        F=prod(F,F);
    }
    g<<R.a[1][0];
    return 0;
}
matr prod(matr A,matr B)
{
    matr R;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            R.a[i][j]=(1LL*A.a[i][0]*B.a[0][j]+1LL*A.a[i][1]*B.a[1][j])%MOD;
    return R;
}