#include <fstream>
#include <cstring>

using namespace std;

const int M = 666013;
int n;

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

void mult(int A[][2],int B[][2] , int C[][2])
{
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
			for(int k=0;k<2;++k)
				C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % M;

}

int fib(int P)
{
	int Z[2][2] , M[2][2] , aux[2][2];
	Z[0][0] = 0;
	Z[0][1] = Z[1][0] = Z[1][1] = 1;
	M[0][1] = M[1][0] = 0;
	M[0][0] = M[1][1] = 1;
	for(int i=0;(1<<i)<=P;++i)
	{
		if((1<<i) & P)
		{
			memset(aux,0,sizeof(aux));
			mult(M,Z,aux);
			memcpy(M,aux,sizeof(aux));
		}
		memset(aux,0,sizeof(aux));
		mult(Z,Z,aux);
		memcpy(Z,aux,sizeof(aux));
	}
	return M[1][1];
}

int main()
{
	fin>>n;
	fout<<fib(n-1)<<'\n';
	return 0;
}