#include <stdio.h>
#define MOD	 666013

void mult(long A[2][2], long B[2][2]) {
	static long C[2][2];
	C[0][0] = (A[0][0]*B[0][0] + A[0][1]*B[1][0]) % MOD;
	C[0][1] = (A[0][0]*B[0][1] + A[0][1]*B[1][1]) % MOD;
	C[1][0] = (A[1][0]*B[0][0] + A[1][1]*B[1][0]) % MOD;
	C[1][1] = (A[1][0]*B[0][1] + A[1][1]*B[1][1]) % MOD;
	
	A[0][0] = C[0][0]; A[0][1] = C[0][1];
	A[1][0] = C[1][0]; A[1][1] = C[1][1];
}

int main() {
	long n;
	
	fscanf(fopen("kfib.in", "r"), "%ld", &n);
	n --;
	
	long P[2][2] = {{1,1},{1,0}};
	long A[2][2] = {{1,0},{0,1}};
	
	int i;
	for (i=1; i<=n; i<<=1) {
		if ( n&i ) 
			mult(A,P);
		mult(P, P);
	}
	
	fprintf(fopen("kfib.out", "w"), "%ld\n", A[0][0]);
	return 0;
}