#include<stdio.h>
#define infile "kfib.in"
#define outfile "kfib.out"
#define modulo 666013
long long a[2][2];
long long b[2][2];
int k; //al catelea termen trebuie cautat

void prod(long long a[2][2], long long b[2][2])
{
	long long c[2][2];
	int i,j,k;
	
	for(i=0;i<2;i++)
		for(j=0;j<2;j++)
			c[i][j]=0;
	
	for(i=0;i<2;i++)
		for(j=0;j<2;j++)
			for(k=0;k<2;k++)
				c[i][j]=(c[i][j]+a[i][k]*b[k][j]) % modulo;
	
	for(i=0;i<2;i++)
		for(j=0;j<2;j++)
			a[i][j]=c[i][j];
}

void read()
{
	scanf("%d\n",&k);
}

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

void solve()
{
	--k;
	while(k)
	{
		if(k&1) prod(a,b);
		prod(b,b);
		k>>=1;
	}
}

void write()
{
	printf("%lld\n",a[0][1]);
}

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	
	read();
	init();
	solve();
	write();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}