#include<cstdio>
#define mod 666013
using namespace std;
int k;
long long a,b=1,c=1,m,n=1,p=1,x,y,z;
int main()
{
	freopen("kfib.in","r",stdin);
	freopen("kfib.out","w",stdout);
	scanf("%d", &k);
	k-=2;
	for(;k;k/=2)
	{
		if(k%2)
		{
			x=(a*m+b*n)%mod;
			y=(a*n+b*p)%mod;
			z=(b*n+c*p)%mod;
			a=x;
			b=y;
			c=z;
		}
		x=(m*m+n*n)%mod;
		y=(m*n+n*p)%mod;
		z=(n*n+p*p)%mod;
		m=x;
		n=y;
		p=z;
	}
	printf("%lld", c);
	return 0;
}