#include<cstdio>
using namespace std;
#define type long long
#define mod 666013
type A[2][2],S[2][2],C[2][2],i,j,q;
FILE *f=freopen("kfib.in","r",stdin),*g=freopen("kfib.out","w",stdout);int k;
void lgput(int k)
{//initialise
	A[0][1]=A[1][0]=A[1][1]=S[1][1]=S[0][0]=1;
	if(!k)printf("%lld",S[0][0]);
	else {
for(;k;k>>=1)
	{if(1&k)	
		{for(i=0;i<2;++i)
			for(j=0;j<2;++j)
				{C[i][j]=0;
				for(q=0;q<2;++q)
					C[i][j]=(C[i][j]+S[i][q]*A[q][j])%mod;
				}
		for(i=0;i<2;++i)
			for(j=0;j<2;++j)
				S[i][j]=C[i][j];
		}
	for(i=0;i<2;++i)
		for(j=0;j<2;++j)
			{C[i][j]=0;
			for(q=0;q<2;++q)
				C[i][j]=(C[i][j]+A[i][q]*A[q][j])%mod;
			}
	for(i=0;i<2;++i)
		for(j=0;j<2;++j)
			A[i][j]=C[i][j];
	}
printf("%lld",S[0][1]);
	}
}
int main()
{
scanf("%d",&k);
lgput(k);
}