#include<fstream>
using namespace std;

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

int f[3][3],m[3][3],aux[3][3];
const int MOD=666013;

void prod(int v[][3], int a[][3], int b[][3])
{
	for (int i=1;i<3;i++)
		for (int j=1;j<3;j++)
		{
			v[i][j]=0;
			for (int k=1;k<3;k++)
				v[i][j]=(v[i][j]+a[i][k]*b[k][j])%MOD;
		}
}

void copy(int a[][3],int b[][3])
{
	for (int i=1;i<3;i++)
		for (int j=1;j<3;j++)
			a[i][j]=b[i][j];
}

int main()
{
	int k;
	in>>k;
	k--;
	m[1][2]=m[2][1]=m[2][2]=1;
	f[1][1]=f[1][2]=1;
	while (k)
	{
		if (k%2)
		{
			prod(aux,f,m);
			copy(f,aux);
		}
		prod(aux,m,m);
		copy(m,aux);
		k/=2;
	}
	out<<f[1][1]<<"\n";
	return 0;
}