#include <cstdio>
#include <cstring>

#define file_in "kfib.in"
#define file_out "kfib.out"

#define mod 666013

int n,a[2][2],b[2][2];

void citire()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &n);
}

void mul(int a[2][2],int b[2][2])
{
	int i,j,k;
	int c[2][2];
	memset(c,0,sizeof(c));
	
	for (i=0;i<2;++i)
		 for (j=0;j<2;++j)
			  for (k=0;k<2;++k)
				   c[i][j]=((long long)c[i][j]+(long long)a[i][k]*b[k][j])%mod;
	memcpy(a,c,sizeof(c));		  
}

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

	n--;
	while(n)
	{
		if (n&1)
			mul(a,b);
		mul(b,b);
		n>>=1;
	}
	
	printf("%d", a[0][0]);
}

int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}