#include<stdio.h>

int x[4]={0, 1, 1 ,1};

int m=666013;

void pmod(int p,long long * r){
	long long y[4];
	long long z[4];
	if(p==1){
		for(int i=0;i<4;i++)
			r[i]=x[i];
		return;
	}
	if(p & 1){
		pmod(p>>1,y);
		z[0]=((y[0]*y[0])%m+(y[1]*y[2])%m)%m;
		z[1]=((y[0]*y[1])%m+(y[1]*y[3])%m)%m;
		z[2]=((y[2]*y[0])%m+(y[3]*y[2])%m)%m;
		z[3]=((y[2]*y[1])%m+(y[3]*y[3])%m)%m;
		r[0]=z[1];
		r[1]=(z[0]+z[1])%m;
		r[2]=z[3];
		r[3]=(z[2]+z[3])%m;
	}
	else{
		pmod(p>>1,y);
		r[0]=((y[0]*y[0])%m+(y[1]*y[2])%m)%m;
		r[1]=((y[0]*y[1])%m+(y[1]*y[3])%m)%m;
		r[2]=((y[2]*y[0])%m+(y[3]*y[2])%m)%m;
		r[3]=((y[2]*y[1])%m+(y[3]*y[3])%m)%m;
	}
}

int main(){

	int K;

	FILE* f= fopen("kfib.in","rt");
	FILE* g= fopen("kfib.out","wt");
	
	fscanf(f,"%d",&K);

	if(K<2){
		fprintf(g,"%d\n",K);
		fclose(g);
		fclose(f);
		return 0;
	}

	long long F[4];
	pmod(K-1,F);

	fprintf(g,"%d\n",F[3]);
	
	fclose(g);
	fclose(f);
	return 0;
}