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

#define p pair<int,int>

const int mo=666013;

int k;

p fib(int k)
{
	if (k==1)
		return make_pair(1,1);
	long long x,y;
	int x0,y0;
	p z;
	if (k%2==0)
	{
		z=fib(k/2);
		x=z.first;
		y=z.second;
		x0=x*(2*y-x)%mo;
		if (x0<0)
			x0+=mo;
		y0=(x*x+y*y)%mo;
		if (y0<0)
			y0+=mo;
		return make_pair(x0,y0);
	}
	else
	{
		z=fib(k/2);
		x=z.first;
		y=z.second;
		x0=x*(2*y-x)%mo;
		if (x0<0)
			x0+=mo;
		y0=(x*x+y*y)%mo;
		if (y0<0)
			y0+=mo;
		return make_pair(y0,(x0+y0)%mo);
	}
}		

int main()
{
	ifstream f("kfib.in");
	ofstream g("kfib.out");
	f >> k;
	if (k==0)
	{
		g << 0;
		return 0;
	}
	g << fib(k).first;
}