#include<fstream>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

long long k,a[3][3],aux[3][3],d[3][3];

void pow(long long b[][3],long long c[][3])
{
	d[1][1]=(long long) b[1][1]*c[1][1]+b[1][2]*c[2][1];
	d[1][2]=(long long) b[1][1]*c[1][2]+b[1][2]*c[2][2];
	d[2][1]=(long long) b[2][1]*c[1][1]+b[2][2]*c[2][1];
	d[2][2]=(long long) b[2][1]*c[1][2]+b[2][2]*c[2][2];

	b[1][1]=d[1][1]%666013;
	b[1][2]=d[1][2]%666013;
	b[2][1]=d[2][1]%666013;
	b[2][2]=d[2][2]%666013;
}

int main()
{
	f>>k;

	a[1][2]=1;
	a[2][1]=1;
	a[2][2]=1;

	aux[1][1]=1;
	aux[2][2]=1;

	while (k!=1)
	{
		if (k%2==0)
		{
			pow(a,a);
			k/=2;
		}
		else
		{
			pow(aux,a);
			k--;
		}
	}
	pow(a,aux);

	g<<a[1][2];
	f.close(); g.close();
	return 0;
}