#include <fstream>
const int MOD = 666013;

std::ifstream in("kfib.in");
std::ofstream out("kfib.out");

struct Matrice {
	int a[2][2];

	friend Matrice operator * (const Matrice& A, const Matrice& B) {
		Matrice C{{0}};
		for (int i = 0; i < 2; ++i)
			for (int j = 0; j < 2; ++j)
				for (int k = 0; k < 2; ++k)
					C.a[i][j] = (C.a[i][j] + 1LL * A.a[i][k] * B.a[k][j]) % MOD;
		return C;
	}

	friend Matrice operator ^ (Matrice A, int p) {
		Matrice res = A;
		--p;
		for (; p; p >>= 1) {
			if (p & 1)
				res = res * A;
			A = A * A;
		}
		return res;
	}
};

int main() {
	int k;
	in >> k;
	Matrice M = {{{1,1},{1,0}}};
	out << (M ^ (k - 1)).a[0][0];
}