#include <cstdio>
#include <vector>
#include <string>
#include <vector>
using namespace std;
const int MOD = 666013;

int N;

int modViaAddition(int value) {
	while (value < 0) {
		value += MOD;
	}
	while (value >= MOD) {
		value -= MOD;
	}

	return value;
}

pair<int, int> getFibN(int N) {
	if (N == 0) {
		return {0, 1};
	}

	pair<int, int> fibNDiv2 = getFibN(N >> 1);
	int fib2N = (1LL * fibNDiv2.first * modViaAddition(fibNDiv2.second - fibNDiv2.first + fibNDiv2.second)) % MOD;
	int fib2NPlus1 = (1LL * fibNDiv2.first * fibNDiv2.first + 1LL * fibNDiv2.second * fibNDiv2.second) % MOD;

	if (N & 1) {
		return {fib2NPlus1, (fib2N + fib2NPlus1) % MOD};
	}
	return {fib2N, fib2NPlus1};
}

int main() {
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);

	scanf("%d", &N);
	printf("%d\n", getFibN(N).first);
	return 0;
}