#include<stdio.h>
#define MOD 666013

int k;
long long S[2][2], Z[2][2];

void inm_sol(long long x1, long long x2, long long x3, long long x4, long long y1, long long y2, long long y3, long long y4){
	
	S[0][0] = ( (x1*y1) + (x2*y3) ) % MOD;
	S[0][1] = ( (x1*y2) + (x2*y4) ) % MOD;
	S[1][0] = ( (x3*y1) + (x4*y3) ) % MOD;
	S[1][1]	= ( (x3*y2) + (x4*y4) ) % MOD;
	
}

void inm_Z(long long x1, long long x2, long long x3, long long x4, long long y1, long long y2, long long y3, long long y4){
	
	Z[0][0] = ( (x1*y1) + (x2*y3) ) % MOD;
	Z[0][1] = ( (x1*y2) + (x2*y4) ) % MOD;
	Z[1][0] = ( (x3*y1) + (x4*y3) ) % MOD;
	Z[1][1]	= ( (x3*y2) + (x4*y4) ) % MOD;
	
}

int main (){
	
	FILE * f = fopen ("kfib.in", "r");
	FILE * g = fopen ("kfib.out", "w");
	
	fscanf(f, "%d", &k);
	k--;
	
	S[0][0] = 1;
	S[1][1] = 1;
	
	Z[0][1] = 1;
	Z[1][0] = 1;
	Z[1][1] = 1;
	
	while(k){
		
		if (k % 2 == 1){
			inm_sol(S[0][0], S[0][1], S[1][0], S[1][1], Z[0][0], Z[0][1], Z[1][0], Z[1][1]);
			k--;
		}
		
		inm_Z(Z[0][0], Z[0][1], Z[1][0], Z[1][1], Z[0][0], Z[0][1], Z[1][0], Z[1][1]);
		k >>= 1;
		
	}
	
	fprintf (g, "%lld", S[1][1]);
	
	fclose(f);
	fclose(g);
	return 0;
	
}