#include<stdio.h>
#define mod 666013
FILE*f=fopen("kfib.in","r");
FILE*g=fopen("kfib.out","w");
long long x[3][3],p[3][3],c[3][3];
int n;
void mult (long long a[][3],long long b[][3])
{
	c[1][1]=c[1][2]=c[2][1]=c[2][2]=0;
	for(int i=1;i<=2;++i)
	{
		c[1][1]+=a[1][i]*b[i][1];
		c[1][1]%=mod;
	}
	for(int i=1;i<=2;++i)
	{
		c[1][2]+=a[1][i]*b[i][2];
		c[1][2]%=mod;
	}
	for(int i=1;i<=2;++i)
	{
		c[2][1]+=a[2][i]*b[i][1];
		c[2][1]%=mod;
	}
	for(int i=1;i<=2;++i)
	{
		c[2][2]+=a[2][i]*b[i][2];
		c[2][2]%=mod;
	}		

	a[1][1]=c[1][1];
	a[1][2]=c[1][2];
	a[2][1]=c[2][1];
	a[2][2]=c[2][2];
}
void put(int n)
{
	p[1][1]=p[2][2]=1;
	x[1][2]=x[2][1]=x[2][2]=1;
	while(n!=0){
		if(n%2==1)
			mult(p,x);
		mult(x,x);
		n/=2;
	}
}
int main()
{
	fscanf(f,"%d",&n);
	
	put(n-1);
	
	fprintf(g,"%lld",p[2][2]);
	
	
	fclose(f);
	fclose(g);
	return 0;
}