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

int main()
{
	int m;
	long long k,p;
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);

	scanf("%lld",&k);
	p=k-1;
	//p=k;
	for(;p!=0;p=p>>1)
	{
		if( (p&1) ==1 )
		{	//sol=(sol*z)%m;
			aux[0][0]= (sol[0][0] * z[0][0])%m	+ (sol[0][1] * z[1][0])%m;
			aux[0][1]= (sol[0][0] * z[0][1])%m	+ (sol[0][1] * z[1][1])%m;
			aux[1][0]= (sol[1][0] * z[0][0])%m	+ (sol[1][1] * z[1][0])%m;
			aux[1][1]= (sol[1][0] * z[0][1])%m	+ (sol[1][1] * z[1][1])%m;
			sol[0][0]=aux[0][0]%m;
			sol[1][0]=aux[1][0]%m;
			sol[0][1]=aux[0][1]%m;
			sol[1][1]=aux[1][1]%m;
			
	//		printf("%ld %ld\n%ld %ld\n",sol[0][0],sol[0][1],sol[1][0],sol[1][1]);
		}
		//z=(z*z)%m;
			aux[0][0]= (z[0][0] * z[0][0])%m + (z[0][1] * z[1][0])%m;
			aux[0][1]= (z[0][0] * z[0][1])%m + (z[0][1] * z[1][1])%m;
			aux[1][0]= (z[1][0] * z[0][0])%m + (z[1][1] * z[1][0])%m;
			aux[1][1]= (z[1][0] * z[0][1])%m + (z[1][1] * z[1][1])%m;
		z[0][0]=aux[0][0]%m;
		z[1][0]=aux[1][0]%m;
		z[0][1]=aux[0][1]%m;
		z[1][1]=aux[1][1]%m;
	}
/*	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("%lld\n",sol[1][1]);
	
	return 0;
}