#include<cstdio>
#define N 666013
void read(),solve();
long long k,x,y,z,t,a,b,c,d,X,Y,Z,T,A,B,C,D;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d",&k);
}
void solve()
{
	x=t=a=b=c=1;
	for(;k;k>>=1)
	{
		if(k&1)
		{
			X=(a*x+b*z)%N;
			Y=(a*y+b*t)%N;
			Z=(c*x+d*z)%N;
			T=(c*y+d*t)%N;
			x=X;y=Y;z=Z;t=T;
		}
		A=(a*a+b*c)%N;
		B=(a*b+b*d)%N;
		C=(c*a+d*c)%N;
		D=(c*b+d*d)%N;
		a=A;b=B;c=C;d=D;
	}
	printf("%d",y);
}