#include <bits/stdc++.h>
using namespace std;
#define ullong unsigned long long
#define MOD 666013
ifstream f("kfib.in");
ofstream g("kfib.out");
struct matrix
{
    ullong a, b, c, d;
    matrix(){}
    matrix(int aa, int bb, int cc, int dd)
    :a(aa), b(bb), c(cc), d(dd){}
    matrix operator*(matrix m)
    {
        matrix r;
        r.a=(a*m.a+b*m.c)%MOD;
        r.b=(a*m.b+b*m.d)%MOD;
        r.c=(c*m.a+d*m.c)%MOD;
        r.d=(c*m.b+d*m.d)%MOD;
        return r;
    }
}Z(0, 1, 1, 1);
matrix pwr(matrix n, ullong p)
{
    matrix x(1, 0, 0, 1);
    for(ullong i=0;(1<<i)<=p;i++)
    {
        if(p&(1<<i))
            x=(x*n);
        n=(n*n);
    }
    return x;
}
int main()
{
    ullong p;
    f>>p;
    if(!p)
    {
        g<<0;
        return 0;
    }
    Z=pwr(Z, p-1);
    g<<Z.d;
    f.close();
    g.close();
    return 0;
}