#include<fstream>
using namespace std;
#define m 666013
ifstream f("kfib.in");
ofstream g("kfib.out");
int k;
struct mat { long aa,bb,cc,dd; }ct,a,b,temp,s,rez;
mat prod( mat a,mat b)
{	rez.aa = ((a.aa * b.aa)%m + (a.bb * b.cc)%m)%m;
	rez.bb = ((a.aa * b.bb)%m + (a.bb * b.dd)%m)%m;
	rez.cc = ((a.cc * b.aa)%m + (a.dd * b.cc)%m)%m;
	rez.dd = ((a.cc * b.bb)%m + (a.dd * b.dd)%m)%m;
	return rez;
}

mat powr(mat a, int k)
{	if(k==1)
		return ct;
	else
		if(k%2)
			return prod(powr(a,k-1),ct);
		else
		{	temp=powr(a,k/2);
			return prod(temp,temp);
		}
}

int main()
{	f>>k;
	k--;
	ct.aa=0; ct.bb=ct.cc=ct.dd=1;
	s=powr(a,k);
	g<<s.dd;
	f.close();
	g.close();
	return 0;
}