#include<stdio.h>
#define m 666013
unsigned int long sol[2][2]={{1,0},{0,1}},aux[2][2],z[2][2]={{0,1},{1,1}};


int main()
{
	int long k,p;
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%ld",&k);
	p=k-1;
	for(;p!=0;p=p>>1)
	{
		if( (p&1) ==1 )
		{	//sol=(sol*z)%m;
			aux[0][0]=(sol[0][0]*z[0][0]+sol[0][1]*z[1][0])%m;
			aux[0][1]=(sol[0][0]*z[0][1]+sol[0][1]*z[1][1])%m;
			aux[1][0]=(sol[1][0]*z[0][0]+sol[1][1]*z[1][0])%m;
			aux[1][1]=(sol[1][0]*z[0][1]+sol[1][1]*z[1][1])%m;
			sol[0][0]=aux[0][0];
			sol[1][0]=aux[1][0];
			sol[0][1]=aux[0][1];
			sol[1][1]=aux[1][1];
		}
		//z=(z*z)%m;
		aux[0][0]=(z[0][0]*z[0][0]+z[0][1]*z[1][0])%m;
		aux[0][1]=(z[0][0]*z[0][1]+z[0][1]*z[1][1])%m;
		aux[1][0]=(z[1][0]*z[0][0]+z[1][1]*z[1][0])%m;
		aux[1][1]=(z[1][0]*z[0][1]+z[1][1]*z[1][1])%m;
		z[0][0]=aux[0][0];
		z[1][0]=aux[1][0];
		z[0][1]=aux[0][1];
		z[1][1]=aux[1][1];
	}
	//printf("%ld %ld\n%ld %ld\n",sol[0][0],sol[0][1],sol[1][0],sol[1][1]);
	//printf("%ld %ld\n%ld %ld\n",z[0][0],z[0][1],z[1][0],z[1][1]);
	printf("%ld\n",sol[1][1]);
	
	return 0;
}