#include<stdio.h>
#define md 666013
int long sol[2][2],a[2][2],m[2][2]={{0,1},{1,1}},I[2][2]={{1,0},{0,1}};

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