#include <cstdio>
using namespace std;
FILE *f,*g;
 
long long n,m,t1,t2,t3,k;
long long r1,r2,r3;

int main()
{
f=fopen("kfib.in","r");
g=fopen("kfib.out","w");
fscanf(f,"%lld%lld",&n);
m=666013;
t1=1;t2=2;
n-=3;
k=2200;r1=1;r2=1;
while(k){--k;r3=r1+r2;r1=r2;r2=r3%m;}
r1%=m;
r2%=m;
r3=r1+r2;
while (n>0)
{
t3=(r2*t1+r3*t2)%m;
t1=(r1*t1+r2*t2)%m;
t2=t3;
n-=2202;
}
while (n<0)
{
t3=t1;
t1=t2-t3;
t2=t3;
if (t1<m) t1+=m;
if (t2<m) t2+=m;
if (t3<m) t3+=m;
++n;
}
fprintf(g,"%lld",t3%m);
}