#include <stdio.h>
#include <string.h>

const char IN[]="kfib.in",OUT[]="kfib.out";
const int mod = 666013;

int N;
int Mat[2][2];

void inm(int A[][2],int B[][2],int C[][2]){
	int i,j,k;
	C[0][0]=C[0][1]=C[1][0]=C[1][1]=0;
	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;
}

void pow(int Mat[][2],int p)
{
	int i;
	static int Sol[2][2];
	static int Aux[2][2];
	Sol[0][0]=Sol[1][1]=1;

	for (i=0;(1<<i)<=p;++i)
	{
		if ((1<<i)&p)
			inm(Sol,Mat,Aux),
			memcpy(Sol,Aux,sizeof(Aux));
		inm(Mat,Mat,Aux);
		memcpy(Mat,Aux,sizeof(Aux));
	}
	memcpy(Mat,Sol,sizeof(Sol));
}

int main()
{
	freopen(IN,"r",stdin);
	scanf("%d",&N);
	fclose(stdin);

	Mat[1][0]=Mat[1][1]=Mat[0][1]=1;
	pow(Mat,N);

	freopen(OUT,"w",stdout);
	printf("%d\n",Mat[0][1]);
	fclose(stdout);

	return 0;
}