#include<fstream>
#define mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int k;
long long sol[3][3],m[3][3],a1,a2,b1,b2;
int main ()
{
	f>>k;
	m[1][2]=m[2][1]=m[2][2]=1;
	k-=2;
	if(k>0)
	{
		while(k)
		{
			if(k%2)
			{
				sol[1][1]=(1LL*m[1][1]*m[1][1]%mod+1LL*m[1][2]*m[2][1]%mod)%mod;
				sol[1][2]=(1LL*m[1][1]*m[1][2]%mod+1LL*m[1][2]*m[2][1]%mod)%mod;
				sol[2][1]=(1LL*m[1][1]*m[2][1]%mod+1LL*m[1][2]*m[2][2]%mod)%mod;
				sol[2][2]=(1LL*m[1][2]*m[2][1]%mod+1LL*m[2][2]*m[2][2]%mod)%mod;
			}
			a1=m[1][1];
			a2=m[1][2];
			b1=m[2][1];
			b2=m[2][2];
			m[1][1]=(1LL*a1*a1%mod+1LL*a2*b1%mod)%mod;
			m[1][2]=(1LL*a1*a2%mod+1LL*a2*b1%mod)%mod;
			m[2][1]=(1LL*a1*b1%mod+1LL*a2*b2%mod)%mod;
			m[2][2]=(1LL*a2*b1%mod+1LL*b2*b2%mod)%mod;
			k/=2;
		}
	}
	else
	{
		if(k==0||k==-1)
			g<<1;
		else
			g<<0;
		return 0;
	}
	if(k%2==0)
	g<<sol[2][1];
	else
		g<<sol[2][2];
	return 0;
}