#include <fstream>

using namespace std;

ifstream fin ("kfib.in");
ofstream fout ("kfib.out");

const int mod = 666013;

int perioada() {
	int a = 0, b = 1, c = a + b;
	for (int i = 0; i < mod * mod; i++) {
		c = (a + b) % mod;
		a = b;
		b = c;
		if (a == 0 && b == 1)
			return i + 1;
	}
}

int main() {
	int n;
	fin >> n;
	int r = n % perioada();
	int first = 0, second = 1;
	int res = r;
	for (int i = 1; i < r; i++) {
		res = (first + second) % mod;
		first = second;
		second = res;
	}
	fout << res % mod;
	return 0;
}