#include<fstream>
using namespace std;

const int modulo=666013;

int main()
{
	long long int k,mat0[2][2],mat1[2][2];

	mat0[0][0]=1;
	mat0[0][1]=1;
	mat0[1][0]=0;
	mat0[1][1]=1;
	mat1[0][0]=1;
	mat1[0][1]=0;
	mat1[1][0]=0;
	mat1[1][1]=1;

	ifstream in("kfib.in");
	ofstream out("kfib.out");
	in>>k;
	if(k==0)
	{
		out<<"0\n";
		out.close();
	}
	else if(k==1)
	{
		out<<"1\n";
		out.close();
	}
	else
	{
		--k;
		while(k)
		{
			if(k&1)
			{
				mat1[0][0]=((mat1[0][0]*mat0[0][0])%modulo+(mat1[0][1]*mat0[1][0])%modulo)%modulo;
				mat1[0][1]=((mat1[0][0]*mat0[0][1])%modulo+(mat1[0][1]*mat0[1][1])%modulo)%modulo;
				mat1[1][0]=((mat1[1][0]*mat0[0][0])%modulo+(mat1[1][1]*mat0[1][0])%modulo)%modulo;
				mat1[1][1]=((mat1[1][0]*mat0[0][1])%modulo+(mat1[1][1]*mat0[1][1])%modulo)%modulo;
			}
			mat0[0][0]=((mat0[0][0]*mat0[0][0])%modulo+(mat0[0][1]*mat0[1][0])%modulo)%modulo;
			mat0[0][1]=((mat0[0][0]*mat0[0][1])%modulo+(mat0[0][1]*mat0[1][1])%modulo)%modulo;
			mat0[1][0]=((mat0[1][0]*mat0[0][0])%modulo+(mat0[1][1]*mat0[1][0])%modulo)%modulo;
			mat0[1][1]=((mat0[1][0]*mat0[0][1])%modulo+(mat0[1][1]*mat0[1][1])%modulo)%modulo;
			k>>=1;
		}
		out<<mat1[0][1]<<"\n";
		out.close();
	}
	in.close();
}