#include <cstdio>
#define N 666013
int main()
{
	int d,i,r;
	long long m[3][3],rez[3][3];
	
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	
	m[1][1]=0;m[1][2]=m[2][1]=m[2][2]=1;
	rez[1][1]=rez[2][2]=1;rez[1][2]=rez[2][1]=0;
	scanf("%d",&i);
	i-=2;
	while (i)
	{
		long long a,b,x;
		if (i%2==1)
		{
			a=(rez[1][1]*m[1][1])%N+(rez[1][2]*m[2][1])%N;
			b=(rez[1][1]*m[1][2])%N+(rez[1][2]*m[2][2])%N;
			x=rez[2][1];
			rez[2][1]=((rez[2][1]*m[1][1])%N+(rez[2][2]*m[2][1])%N)%N;
			rez[2][2]=((x*m[1][2])%N+(rez[2][2]*m[2][2])%N)%N;
			rez[1][1]=a%N;rez[1][2]=b%N;
		}
		a=(m[1][1]*m[1][1])%N+(m[1][2]*m[2][1])%N;
		b=(m[1][1]*m[1][2])%N+(m[1][2]*m[2][2])%N;
		x=m[2][1];
		m[2][1]=((m[2][1]*m[1][1])%N+(m[2][2]*m[2][1])%N)%N;
		m[2][2]=((x*m[1][2])%N+(m[2][2]*m[2][2])%N)%N;
		m[1][1]=a%N;m[1][2]=b%N;
		
		i/=2;
	}
	rez[0][0]=(rez[1][2]+rez[2][2])%N;
	printf("%lld",rez[0][0]);
return 0;
}