# include <cstdio>
# define MOD 666013
using namespace std;
long long k,S[2][2],C[2][2],A[2][2],i,j,q;
FILE *f=freopen("kfib.in","r",stdin),*g=freopen("kfib.out","w",stdout);
void al_k_termen()
{
	for(i=0;i<2;++i)
	{
		A[1][i]=1;
		S[i][i]=1;
	}
	A[0][1]=1;
	for(;k;k>>=1)
	{
		if(k%2)
		{
			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("%lld",&k);
	al_k_termen();
}