#include<iostream>
#include<fstream>
using namespace std;
fstream f("kfib.in",ios::in), g("kfib.out",ios::out);
long long mat[5][5],b[5][5],pu,mod=666013;
void matmat(long long x[5][5],long long y[5][5]);
void matpro(long long x[5][5],long long nr);
void putere(long long a[5][5],long long p,long long m);
int main()
{
	mat[1][2]=mat[2][1]=mat[2][2]=1;
	b[1][2]=b[2][1]=b[2][2]=1;
	f>>pu;
	putere(mat,pu-1,mod);
	//cout<<mat[2][2];
	g<<mat[2][2];
	return 0;
}
void matmat(long long x[5][5],long long y[5][5])
{
	long long nr1,nr2,nr3;
	nr1=x[1][1]*y[1][1]+x[1][2]*y[2][1];
	nr2=x[1][1]*y[1][2]+x[1][2]*y[2][2];
	nr3=x[2][1]*y[1][2]+x[2][2]*y[2][2];
	x[1][1]=nr1;x[1][2]=x[2][1]=nr2;x[2][2]=nr3;
}
void matpro(long long x[5][5],long long nr)
{
	x[1][1]%=nr;
	x[1][2]%=nr;
	x[2][1]=x[1][2];
	x[2][2]%=nr;
}
void putere(long long a[5][5],long long p,long long m)
{
	if(p>1)
	{
		putere(a,p/2,m);
		matmat(a,a);
		matpro(a,m);
		if(p%2)
			matmat(a,b);
		matpro(a,m);
	}	
}