#include <fstream>
#include <string.h>

using namespace std;

const char InFile[]="kfib.in";
const char OutFile[]="kfib.out";
const int MOD=666013;

ifstream fin(InFile);
ofstream fout(OutFile);

int M[3][3],SOL[3][3],n;

void m_mul(int A[3][3],int B[3][3],int C[3][3])
{
	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])%MOD;
			}
		}
	}
}

void lg_fib(int p,int SOL[3][3])
{
	int C[3][3],AUX[3][3];
	memcpy(C,M,sizeof(M));
	SOL[1][1]=SOL[0][0]=1;
	
	for(int i=0;(1<<i)<=p;++i)
	{
		if((1<<i)&p)
		{
			memset(AUX,0,sizeof(AUX));
			m_mul(SOL,C,AUX);
			memcpy(SOL,AUX,sizeof(AUX));
		}
		memset(AUX,0,sizeof(AUX));
		m_mul(C,C,AUX);
		memcpy(C,AUX,sizeof(C));
	}
}

int main()
{
	fin>>n;
	fin.close();
	
	M[0][0]=0;
	M[0][1]=M[1][0]=M[1][1]=1;
	
	lg_fib(n-1,SOL);
	
	fout<<SOL[1][1];
	fout.close();
	return 0;
}