#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long k,MOD;
struct tip
{
    long long v[3][3];
};
tip def,m;
tip inmt(tip x,tip y)
{
    tip aux;
    aux.v[1][1]=((x.v[1][1]*y.v[1][1]) + (x.v[1][2]*y.v[2][1]))%MOD;
    aux.v[1][2]=((x.v[1][1]*y.v[1][2]) + (x.v[1][2]*y.v[2][2]))%MOD;
    aux.v[2][1]=((x.v[2][1]*y.v[1][1]) + (x.v[2][2]*y.v[2][1]))%MOD;
    aux.v[2][2]=((x.v[2][1]*y.v[1][2]) + (x.v[2][2]*y.v[2][2]))%MOD;
    return aux;
}

tip rise(tip a,long long b)
{
    if(b ==1)
        return def;
    tip x = rise(a, b / 2);
    if(b % 2 == 0)
    {
        x=inmt(x,x);
        return x;
    }
    else
    {
        x=inmt(x,x);
        return (inmt(x,a));
    }

}
int main()
{
    fin>>k;
    MOD=666013;
    def.v[1][1]=0;
    def.v[1][2]=1;
    def.v[2][1]=1;
    def.v[2][2]=1;
    m=def;
    m=rise(m,k);
    long long f0=0,f1=1;
    long long fn,fn1;
    fn =((f0*m.v[1][1]) + (f1*m.v[2][1]))%MOD;
    fn1=((f0*m.v[1][2]) + (f1*m.v[2][2]))%MOD;
    fout<<fn<<'\n';
    return 0;
}