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

#define MOD 666013

FILE*f=fopen("kfib.in","r");
FILE*g=fopen("kfib.out","w");

int k,p,i,j,S[3][3],P[3][3],C[3][3];

inline void inmultire ( int A[3][3] , int B[3][3] ){
	
	C[1][1] = (1LL*A[1][1] * B[1][1] + 1LL*A[1][2] * B[2][1]) % MOD;
	C[1][2] = (1LL*A[1][1] * B[1][2] + 1LL*A[1][2] * B[2][2]) % MOD;
	C[2][1] = (1LL*A[2][1] * B[1][1] + 1LL*A[2][2] * B[1][2]) % MOD;
	C[2][2] = (1LL*A[2][1] * B[1][2] + 1LL*A[2][2] * B[2][2]) % MOD;
	
	memcpy(A,C,sizeof(C));
	
}

int main () {
	
	fscanf(f,"%d",&k);
	
	p = k - 1; 
	P[1][1] = P[1][2] = P[2][1] = 1; P[2][2] = 0;
	S[1][1] = S[1][2] = S[2][1] = S[2][2] = 0;
	
	while ( p ) {
		if ( p & 1 ){
			if ( !S[1][1] )
				memcpy(S,P,sizeof(P));
			else 
				inmultire(S,P);
		}
		inmultire(P,P);
		p = p >> 1;
	}
	
	fprintf(g,"%d\n",S[1][1]);
	
	fclose(f);
	fclose(g);
	
	return 0;
}