#include<cstdio>
using namespace std;
FILE*in=fopen("kfib.in","r");
FILE*out=fopen("kfib.out","w");
const int mod=666013;
int k;  ////////////////////( a  b )
        ////////////////////( c  d )
        /////////////( a  b )
        /////////////( c  d )

long long a=0,b=1,c=1,d=1;
long long v=0,w=1;
void sq()
{
    long long x=(long long)((long long)(a*a)+(long long)(b*c));
    long long y=(long long)((long long)(a*b)+(long long)(b*d));
    long long z=(long long)((long long)(a*c)+(long long)(c*d));
    long long t=(long long)((long long)(c*b)+(long long)(d*d));
    x=(long long)(x%mod);
    y=(long long)(y%mod);
    z=(long long)(z%mod);
    t=(long long)(t%mod);
    a=(long long)x;
    b=(long long)y;
    c=(long long)z;
    d=(long long)t;
}
int main()
{
    fscanf(in,"%d",&k);
    while(k>0)
    {
        if(k%2==1)
        {
            long long vv=(long long)((long long)(v*a)+(long long)(w*c));
            long long ww=(long long)((long long)(v*b)+(long long)(w*d));
            vv=(long long)(vv%mod);
            ww=(long long)(ww%mod);
            v=(long long)vv;
            w=(long long)ww;
        }
        sq();
        k=k/2;
    }
    fprintf(out,"%lld",v);
}