#include <cstdio>
#include <cstring>
using namespace std;
#define MOD 666013
int K,M[3][3],Ms[3][3],Maux[3][3],F[3][3];

void inmultire(int A[][3], int B[3][3], int C[3][3])
{ int i,j,k;
	for (i=0;i<2;++i)
	 for (j=0;j<2;++j)
	  for (k=0;k<2;++k)
		C[i][j]=(C[i][j]+1LL*A[i][k]*B[k][j])%MOD;
}

int main()
{
	freopen("kfib.in","r",stdin);	
	scanf("%d",&K);
	
	M[0][0]=0; M[0][1]=M[1][0]=M[1][1]=1;
	Ms[0][0]=Ms[1][1]=1; Ms[0][1]=Ms[1][0]=0;
	--K;
	
	int i;
	for (i=0; (1<<i)<=K; ++i)
	{
	  if (K&(1<<i))
	 	 {
		   memset(Maux,0,sizeof(Maux));
		   inmultire(Ms,M,Maux);
		   memcpy(Ms,Maux,sizeof(Ms));
		 } 
	  
	  memset(Maux,0,sizeof(Maux));
	  inmultire(M,M,Maux);
	  memcpy(M,Maux,sizeof(M));
	}
	
	F[0][0]=F[0][1]=1;
	memset(Maux,0,sizeof(Maux));
	inmultire(F,Ms,Maux);
	
	freopen("kfib.out","w",stdout);
	printf("%d",Maux[0][0]);
	return 0;
}