using namespace std;
#include<fstream>
#define MOD 666013
int K, rez[4][4], c[4][4];
void mul(int a[][4], int b[][4]) // a = a * b
{
	int r[4][4],i,j,k;	
	for(i=1; i<=2;++i)
		for(j=1;j<=2;++j)
			for(r[i][j] = 0, k=1; k<=2;++k)
				r[i][j] = (r[i][j] + (a[i][k] * b[k][j]) %MOD) %MOD;
	for(i=1;i<=2;++i)
		for(j=1;j<=2;++j)
			a[i][j] = r[i][j] % MOD;
}
int main()
{
	ifstream f("kfib.in");
	ofstream g("kfib.out");
	f>>K;
	c[1][1] = 0; c[1][2] = c[2][2] = c[2][1] = 1;
	rez[1][1] = rez[2][2] = 1;
	--K;
	if(K == 0) { g<<"0\n"; return 0; }
	while(K)
	{
		if(K&1)
		{
			--K;
			mul(rez,c);
		}
		else
		{
			K>>=1;
			mul(c,c);
		}
	}
	g<<rez[2][2]<<"\n";
	return 0;
}