#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);
	return 0;
}