#include<stdio.h>
#define m 666013
long long z[2][2]={{0,1},{1,1}}, aux[2][2],sol[2][2]={ {1,0},{0,1} };
int main()
{
	int p;
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d",&p);
	p--;
	while(p!=0)
	{
		if((p&1)==1)
		{
		//actualizeaza solutia
		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;
		
		}
		// ridica matricea la patrat
		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;
		
		p=p>>1;
	}
	printf("%lld\n",sol[1][1]);
	return 0;
}