#include<fstream>
#include<iostream>
using namespace std;
#define mod 666013
int i,k;
long long m[2],n[3][3];
int main()
{
	ifstream fin("kfib.in");
	fin>>k;
	fin.close();
	n[1][1]=0;//facem initializarile
	n[1][2]=n[2][1]=n[2][2]=1;
	m[1]=m[2]=1;//vectorul solutie
	--k;
	for(i=0;(1<<i)<=k;++i)
	{
		if ((1<<i)&k)//operatie pe biti(foarte rapida)
		{
			m[0]=m[1];//ca sa nu stric valoarea lui m[2]
			m[1]=((m[1]*n[1][1])%mod+(m[2]*n[2][1])%mod)%mod;
			m[2]=((m[0]*n[1][2])%mod+(m[2]*n[2][2])%mod)%mod;
		}
		//nu e bun pt ca trebuie ridicat la patrat
		/*n[2][2]=(n[2][1]+n[2][2])%mod;//smecherie
		n[2][1]=(n[1][1]+n[1][2])%mod;		
		n[1][1]=n[1][2];
		n[1][2]=n[2][1];
		*/
		m[0]=n[2][2];//smecherie ca sa nu stric valorile
		n[2][2]=((n[2][1]*n[1][2])%mod+(n[2][2]*n[2][2])%mod)%mod;
		n[2][1]=((n[2][1]*n[1][1])%mod+(m[0]*n[2][1])%mod)%mod;
		n[1][1]=((n[1][1]*n[1][1])%mod+(n[1][2]*n[1][2])%mod)%mod;
		n[1][2]=n[2][1];
	}
	FILE *fout=fopen("kfib.out","w");
	fprintf(fout,"%d",m[1]);
	fclose(fout);
	return 0;
}