#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]=sol[1][2]=sol[2][2]=sol[2][1]=1;
	while(k)
		{
			if(k%2)
			{
				a1=sol[1][1];
				a2=sol[1][2];
				b1=sol[2][1];
				b2=sol[2][2];
				sol[1][1]=(a1*m[1][1]%mod+a2*m[2][1]%mod)%mod;
				sol[1][2]=(a1*m[1][2]%mod+a2*m[2][2]%mod)%mod;
				sol[2][1]=(b1*m[1][1]%mod+b2*m[2][1]%mod)%mod;
				sol[2][2]=(b1*m[1][2]%mod+b2*m[2][2]%mod)%mod;
			}
			a1=m[1][1];
			a2=m[1][2];
			b1=m[2][1];
			b2=m[2][2];
			m[1][1]=(a1*a1%mod+a2*b1%mod)%mod;
			m[1][2]=(a1*a2%mod+a2*b2%mod)%mod;
			m[2][1]=(a1*b1%mod+a2*b2%mod)%mod;
			m[2][2]=(a2*b1%mod+b2*b2%mod)%mod;
			k/=2;
		}
	g<<sol[1][1];
	return 0;
}