#include <stdio.h>

const int MAXN = 1000000001;
const int KMOD = 666013;

void multm2 (long long A[2][2], long long B[2][2])
{
	long long TMP[2][2];	
	TMP[0][0] = ( A[0][0] * B[0][0]  +  A[0][1] * B[1][0] ) % KMOD;
	TMP[0][1] = ( A[0][0] * B[0][1]  +  A[0][1] * B[1][1] ) % KMOD;
	TMP[1][0] = ( A[1][0] * B[0][0]  +  A[1][1] * B[1][0] ) % KMOD;
	TMP[1][1] = ( A[1][0] * B[0][1]  +  A[1][1] * B[1][1] ) % KMOD;	
	A[0][0]=TMP[0][0];
	A[0][1]=TMP[0][1];
	A[1][0]=TMP[1][0];
	A[1][1]=TMP[1][1];
}

int main()
{
	FILE *input=fopen("kfib.in","r");
	FILE *output=fopen("kfib.out","w");
	
	long long F[2][2],X[2][2],Y[2][2];
	int N,K;
	
	F[0][0]=0; F[0][1]=1; F[1][0]=0; F[1][1]=0;
	X[0][0]=1; X[0][1]=0; X[1][0]=0; X[1][1]=1;
	Y[0][0]=0; Y[0][1]=1; Y[1][0]=1; Y[1][1]=1;
	
	fscanf(input,"%d%d",&N); N--;
	
	for (K=1; K <=N; K*=2)
	{
		if (K & N)
			multm2(X,Y);
		multm2(Y,Y);		
	}
	
	multm2(F,X);
	
	if (N+1==0) fprintf(output,"0\n");
	if (N+1==1) fprintf(output,"1\n");
	if (N+1>1 ) fprintf(output,"%lld\n",F[0][1] % KMOD);
	
	fclose(input);
	fclose(output);
	return 0;
}