#include<fstream>
#define mod 666013
using namespace std;

long long k, i, j, d, v[3][3], rez[3][3], a[3][3];

ifstream fin("kfib.in");
ofstream fout("kfib.out");

int main()
{
	fin>>k;
	k=k-2;
	rez[1][1]=rez[2][2]=v[1][2]=v[2][1]=v[2][2]=1;
	while(k)
	{
		if(k%2==0)
		{
			a[1][1]=v[1][1]*v[1][1]+v[1][2]*v[2][1];
			a[1][2]=v[1][1]*v[1][2]+v[1][2]*v[2][2];
			a[2][1]=v[1][2]*v[1][1]+v[2][2]*v[1][2];
			a[2][2]=v[1][2]*v[1][2]+v[2][2]*v[2][2];
			for(i=1;i<=2;i++)
				for(j=1;j<=2;j++)
					v[i][j]=a[i][j]%mod;
			k/=2;
		}
		else
		{
			k--;
			a[1][1]=rez[1][1]*v[1][1]+rez[1][2]*v[2][1];
			a[1][2]=rez[1][1]*v[1][2]+rez[1][2]*v[2][2];
			a[2][1]=rez[1][2]*v[1][1]+rez[2][2]*v[1][2];
			a[2][2]=rez[1][2]*v[1][2]+rez[2][2]*v[2][2];
			for(i=1;i<=2;i++)
				for(j=1;j<=2;j++)
					rez[i][j]=a[i][j]%mod;
			
		}
	}
	fout<<(rez[1][2]+rez[2][2])%mod<<'\n';
	fin.close();
	fout.close();
	return 0;
}