#include<fstream>

using namespace std;

const int MOD = 666013;
bool binary[30];

void dtob(int x, short& i) {
	if (x % 2) binary[i] = true;
	if (x / 2) dtob(x / 2, ++i);
}

int main() {
	ifstream in("kfib.in");
	ofstream out("kfib.out");

	int k; short n=0;
	in >> k;
	k -= 2;
	dtob(k,n);

	int elozo[2][2], jelenlegi[2][2], result[2][2];
	jelenlegi[0][0] = 0;
	jelenlegi[0][1] = 1;
	jelenlegi[1][0] = 1;
	jelenlegi[1][1] = 1;

	result[0][0] = 1;
	result[0][1] = 0;
	result[1][0] = 0;
	result[1][1] = 1;

	for (short i = 0;i <= n;++i) {
		for (short j = 0;j < 2;++j)
			for (short t = 0; t < 2; ++t)
				elozo[j][t] = jelenlegi[j][t];
		if (i > 0) {
			jelenlegi[0][0] = (((elozo[0][0] * elozo[0][0]) % MOD) + ((elozo[0][1] * elozo[1][0]) % MOD)) % MOD;
			jelenlegi[0][1] = (((elozo[0][0] * elozo[0][1]) % MOD) + ((elozo[0][1] * elozo[1][1]) % MOD)) % MOD;
			jelenlegi[1][0] = (((elozo[1][0] * elozo[0][0]) % MOD) + ((elozo[1][1] * elozo[1][0]) % MOD)) % MOD;
			jelenlegi[1][1] = (((elozo[1][0] * elozo[0][1]) % MOD) + ((elozo[1][1] * elozo[1][1]) % MOD)) % MOD;
		}
		int temp[2][2];
		if (binary[i]) {
			temp[0][0] = (((jelenlegi[0][0] * result[0][0]) % MOD) + ((jelenlegi[0][1] * result[1][0]) % MOD)) % MOD;
			temp[0][1] = (((jelenlegi[0][0] * result[0][1]) % MOD) + ((jelenlegi[0][1] * result[1][1]) % MOD)) % MOD;
			temp[1][0] = (((jelenlegi[1][0] * result[0][0]) % MOD) + ((jelenlegi[1][1] * result[1][0]) % MOD)) % MOD;
			temp[1][1] = (((jelenlegi[1][0] * result[0][1]) % MOD) + ((jelenlegi[1][1] * result[1][1]) % MOD)) % MOD;
		}
		for (short j = 0;j < 2;++j)
			for (short t = 0; t < 2; ++t)
				result[j][t] = temp[j][t];
	}

	out << (result[0][1] + result[1][1]) % MOD;
}