#include<fstream>
#include<iostream>
using namespace std;

const int modulo=666013;

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

	mat0[0][0]=0;
	mat0[0][1]=1;
	mat0[1][0]=1;
	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)
			{
				mat3[0][0]=((mat1[0][0]*mat0[0][0])%modulo+(mat1[0][1]*mat0[1][0])%modulo)%modulo;
				mat3[0][1]=((mat1[0][0]*mat0[0][1])%modulo+(mat1[0][1]*mat0[1][1])%modulo)%modulo;
				mat3[1][0]=((mat1[1][0]*mat0[0][0])%modulo+(mat1[1][1]*mat0[1][0])%modulo)%modulo;
				mat3[1][1]=((mat1[1][0]*mat0[0][1])%modulo+(mat1[1][1]*mat0[1][1])%modulo)%modulo;
				for(int i=0;i<2;i++)
					for(int j=0;j<2;j++)
						mat1[i][j]=mat3[i][j];
			}
			mat3[0][0]=((mat0[0][0]*mat0[0][0])%modulo+(mat0[0][1]*mat0[1][0])%modulo)%modulo;
			mat3[0][1]=((mat0[0][0]*mat0[0][1])%modulo+(mat0[0][1]*mat0[1][1])%modulo)%modulo;
			mat3[1][0]=((mat0[1][0]*mat0[0][0])%modulo+(mat0[1][1]*mat0[1][0])%modulo)%modulo;
			mat3[1][1]=((mat0[1][0]*mat0[0][1])%modulo+(mat0[1][1]*mat0[1][1])%modulo)%modulo;
			for(int i=0;i<2;i++)
				for(int j=0;j<2;j++)
					mat0[i][j]=mat3[i][j];
			k>>=1;
		}
		out<<mat1[1][1]<<"\n";
		out.close();
	}
	in.close();
}