#include<fstream>
using namespace std;

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

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

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

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

int main()
{
	long long 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;
}