#include <fstream>
#include <iostream>

#define MOD 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long n, v[3]={0,1,1}, vr[3], A[3][3], Ar[3][3], Aux[3][3], Zero[3][3];

void multiply(long long A[3][3],long long B[3][3],long long C[3][3])
{
	int i,j,k;
	for(i=1;i<=2;i++)
		for(j=1;j<=2;j++)
			for(k=1;k<=2;k++)
				C[i][j]+=(A[i][k]*B[k][j])%MOD;
}

void muta(long long A[3][3],long long B[3][3])
{
	int i,j;
	for(i=1;i<=2;i++)
		for(j=1;j<=2;j++)
			A[i][j]=B[i][j];
		
	for(i=1;i<=2;i++)
		for(j=1;j<=2;j++)
			B[i][j]=0;
}

int main()
{
	f>>n;
	A[1][1]=A[1][2]=A[2][1]=1;
	Ar[1][1]=Ar[2][2]=1;
	
	if(n==1 || n==0) {g<<1; return 0;}
	
	n=n-1;
	while(n>1)
	{
		if(n%2==0)
		{
			multiply(A,A,Aux); muta(A,Aux);
			n=n/2;
		}
		else
		{
			multiply(Ar,A,Aux);muta(Ar,Aux); 
			multiply(A,A,Aux); muta(A,Aux); 
			
			n=n/2;
		}
	}
	multiply(A,Ar,Aux); muta(Ar,Aux);
	g<<Ar[1][1];
	
}