#include<fstream.h>
#define m 666013
ifstream f("kfib.in");
ofstream g("kfib.out");
long long k,a[2][2],c[2][2],sol[2][2],sol1[2][2];

void init()
{
	a[0][0]=0;
	a[0][1]=1;
	a[1][0]=1;
	a[1][1]=1;
}

void inmultire(long long  x[][2],long long  y[][2], long long  z[][2])
{
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
		{
			z[i][j]=0;
			for(int k=0;k<2;k++)
				z[i][j]=(z[i][j]+(x[i][k]*y[k][j])%m)%m;
		}
}

void atrib(long long  x[][2], long long  y[][2])
{
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			x[i][j]=y[i][j];
}

int main()
{
	f>>k;
	init();
	sol[0][0]=1;
	sol[1][1]=1;
	for(int i=31;i>=0;i--)
	{	
		inmultire(sol,sol,sol1);
		atrib(sol,sol1);
		if((1<<i&(k-2))!=0)
		{
			inmultire(sol,a,sol1);
			atrib(sol,sol1);
		}
	}
	g<<(sol[0][1]+sol[1][1])%m<<'\n';
	g.close();
	return 0;
}