#include<fstream>
#include<iostream>
#include<math.h>
using namespace std;
long long pow2(long long p)
{
	if(p==0)return 1;
	return 2<<(p-1);
}
int main()
{

	ifstream f("kfib.in");
	ofstream g("kfib.out");
	long long k,p,l,i,mod=666013;
	long long z[66][3][3],a[3][3],temp[3][3];
	f>>k;
	z[0][1][1]=0;
	z[0][1][2]=z[0][2][1]=z[0][2][2]=1;
	l=(int)log2(k);
	for(p=1;p<=l;++p)
	{
		z[p][1][1]=(z[p-1][1][1]*z[p-1][1][1]+z[p-1][1][2]*z[p-1][2][1])%mod;
		z[p][1][2]=(z[p-1][1][1]*z[p-1][1][2]+z[p-1][1][2]*z[p-1][2][2])%mod;
		z[p][2][1]=(z[p-1][2][1]*z[p-1][1][1]+z[p-1][2][2]*z[p-1][2][1])%mod;
		z[p][2][2]=(z[p-1][2][1]*z[p-1][1][2]+z[p-1][2][2]*z[p-1][2][2])%mod;
	}
	a[1][1]=z[l][1][1];
	a[1][2]=z[l][1][2];
	a[2][1]=z[l][2][1];
	a[2][2]=z[l][2][2];
	p=pow2(l);
	while(p!=k)
	{
		i=(int)log2(k-p);
		temp[1][1]=(a[1][1]*z[i][1][1]+a[1][2]*z[i][2][1])%mod;
		temp[1][2]=(a[1][1]*z[i][1][2]+a[1][2]*z[i][2][2])%mod;
		temp[2][1]=(a[2][1]*z[i][1][1]+a[2][2]*z[i][2][1])%mod;
		temp[2][2]=(a[2][1]*z[i][1][2]+a[2][2]*z[i][2][2])%mod;
		a[1][1]=temp[1][1];
		a[1][2]=temp[1][2];
		a[2][1]=temp[2][1];
		a[2][2]=temp[2][2];
		p+=pow2(i);
	}
	g<<a[1][2];
	f.close();
	g.close();
	return 0;
}