#include <iostream>
#include <stdio.h>
using namespace std;

#define modulo(x)	((x) % 666013)

int main() {
	long int k, top = 0, putere[4] = {0, 1, 1, 1}, v[4] = {1, 0, 0, 1}, dummy[4];
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);
	scanf("%ld", &k);
	while(k) {
		if(k % 2) {
			dummy[0] = modulo(v[0]) * modulo(putere[0]) + modulo(v[1]) * modulo(putere[2]);
			dummy[1] = modulo(v[0]) * modulo(putere[1]) + modulo(v[1]) * modulo(putere[3]);
			dummy[2] = modulo(v[2]) * modulo(putere[0]) + modulo(v[3]) * modulo(putere[2]);
			dummy[3] = modulo(v[2]) * modulo(putere[1]) + modulo(v[3]) * modulo(putere[3]);

			v[0] = modulo(dummy[0]);
			v[1] = modulo(dummy[1]);
			v[2] = modulo(dummy[2]);
			v[3] = modulo(dummy[3]);
		}

		k >>= 1;

		dummy[0] = modulo(putere[0]) * modulo(putere[0]) + modulo(putere[1]) * modulo(putere[2]);
		dummy[1] = modulo(putere[0]) * modulo(putere[1]) + modulo(putere[1]) * modulo(putere[3]);
		dummy[2] = modulo(putere[2]) * modulo(putere[0]) + modulo(putere[3]) * modulo(putere[2]);
		dummy[3] = modulo(putere[2]) * modulo(putere[1]) + modulo(putere[3]) * modulo(putere[3]);

		putere[0] = modulo(dummy[0]);
		putere[1] = modulo(dummy[1]);
		putere[2] = modulo(dummy[2]);
		putere[3] = modulo(dummy[3]);
	}
	
	printf("%ld\n", v[2]);
	return 0;
}