#include <iostream>
#include <fstream>

const int MODULO = 666013;

struct Matrice {

	int N;
	int M;

	long long int mat[3][3] = {};
};

Matrice A;

Matrice prod(Matrice X, Matrice Y) {

	Matrice C;
	for (int i = 1; i <= 2; ++i) {

		for (int j = 1; j <= 2; ++j) {

			for (int k = 1; k <= 2; ++k)
			{
				C.mat[i][j] = (C.mat[i][j] + X.mat[i][k]  * Y.mat[k][j]) % MODULO;
			}
		}

	}

	return C;

}

Matrice pow(Matrice A, int p) {

	if (p == 0) {
		A.mat[1][1] = 1;
		A.mat[1][2] = 0;
		A.mat[2][1] = 0;
		A.mat[2][2] = 1;
		return A;
	}

	if (p % 2 == 0) {
		return pow(prod(A, A), p / 2);
	}
	return prod(A, pow(prod(A, A), p / 2));
}


int main() {

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

	long long int K;
	in >> K;

	A.mat[1][1] = 1;
	A.mat[1][2] = 1;
	A.mat[2][1] = 1;
	A.mat[2][2] = 0;

	Matrice Sol = pow(A, K - 1);

	out << Sol.mat[1][1];

	system("PAUSE");
	return 0;
}