#include<cstdio>
void read(),solve();
long long a,b,c,d,m,n,p,q,A,B,C,D,M;
int k;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d",&k);
}
void solve()
{
	a=b=c=1;
	m=q=1;
	M=666013;
	for(;k;k>>=1)
	{
		if(k&1)
		{
			A=(m*a+n*c)%M;
			B=(m*b+n*d)%M;
			C=(p*a+c*q)%M;
			D=(p*b+d*q)%M;
			m=A;
			n=B;
			p=C;
			q=D;
		}
		A=(a*a+b*c)%M;
		B=(a*b+b*d)%M;
		C=(a*c+c*d)%M;
		D=(b*c+d*d)%M;
		a=A;
		b=B;
		c=C;
		d=D;
	}
	printf("%lld\n",n);
}