#include <fstream.h>
#define MOD 666013
ifstream f("kfib.in");
ofstream g("kfib.out");
unsigned long long n,A[2][2],P[2][2],R[2][2];
void inmultire(unsigned long long R[2][2], unsigned long long  A[2][2],unsigned long long P[2][2])
{
	R[0][0]=(A[0][0]*P[0][0] + A[0][1]*P[1][0])%MOD;
	R[0][1]=(A[0][0]*P[0][1] + A[0][1]*P[1][1])%MOD;
	R[1][0]=(A[1][0]*P[0][0] + A[1][1]*P[1][0])%MOD;
	R[1][1]=(A[1][0]*P[0][1] + A[1][1]*P[1][1])%MOD;
}
void egalitate(unsigned long long A[2][2],unsigned long long B[2][2])
{
	for(int i=0;i<=1;i++)
		for(int j=0;j<=1;j++)
			A[i][j]=B[i][j];
}
int main()
{
	f>>n;
	P[0][0]=1;
	P[0][1]=0;
	P[1][0]=0;
	P[1][1]=1;
	A[0][0]=0;
	A[0][1]=1;
	A[1][0]=1;
	A[1][1]=1;
	while(n)
	{
		if(n%2==1)
		{
			inmultire(R,P,A);
			egalitate(P,R);
		}
		inmultire(R,A,A);
		egalitate(A,R);
		n/=2;
	}
	g<<P[0][1];
        f.close();
        g.close();
	return 0;
}