#include<stdio.h>

FILE *f=fopen( "kfib.in","r");
FILE *g=fopen("kfib.out","w");

void szorzas(long long a[5][5], long long b[5][5]);
long long c[5][5]={0};
long long t[5][5]={0};
int main()
{
	long long n;
	long long a[5][5]={0};
	long long b[5][5]={0};
	
	fscanf(f,"%ld",&n);
	b[1][1]=0;	b[1][2]=1;
	b[2][1]=1;	b[2][2]=1;
	
	c[1][1]=1;  c[1][2]=0;
	c[2][1]=0;	c[2][2]=1;
	
	t[1][1]=1;  t[1][2]=0;
	t[2][1]=0;	t[2][2]=1;
	if(n==0)fprintf(g,"0");
	if(n==1)fprintf(g,"1");
	if(n==2)fprintf(g,"1");
	if(n<3){return 0;}
	n-=3;
	while(n)
	{
		if(n%2)	
		{
			szorzas(b,t);
			t[1][1]=c[1][1];
			t[1][2]=c[1][2];
			t[2][1]=c[2][1];
			t[2][2]=c[2][2];
		}
		szorzas(b,b);
		b[1][1]=c[1][1];
		b[1][2]=c[1][2];
		b[2][1]=c[2][1];
		b[2][2]=c[2][2];
		n/=2;
	}
	fprintf(g,"%ld",(t[2][1]+t[2][2])%666013);
	return 0;
}

void szorzas(long long a[5][5], long long b[5][5])
{
	int i,j,k;
	c[1][1]=0;
	c[1][2]=0;
	c[2][1]=0;
	c[2][2]=0;
	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];
				c[i][j]=c[i][j]%666013;
			}
}