#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 )

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