#include <fstream>

#define MOD 666013

using namespace std;

void mult_mat(long long m1[2][2], long long m2[2][2]) {
	long long res[2][2];
	res[0][0] = (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % MOD;
	res[0][1] = (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % MOD;
	res[1][0] = (m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % MOD;
	res[1][1] = (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % MOD;
	m1[0][0] = res[0][0];
	m1[0][1] = res[0][1];
	m1[1][0] = res[1][0];
	m1[1][1] = res[1][1];
}

void expo(long long res[2][2], long long m[2][2], long long n)
{
	long long c = 1;
	res[0][0] = 1;
	res[0][1] = 0;
	res[1][0] = 0;
	res[1][1] = 1;

	while (true) {
		if (c & n) {
			mult_mat(res, m);
		}
		mult_mat(m, m);
		c = c << 1;
		if (c > n)
			break;
	}
}

int main(void)
{
	ifstream f("kfib.in");

	long long k;
	f >> k;
	
	f.close();

	long long m[2][2] = {{0, 1}, {1, 1}};
	long long res[2][2];
	expo(res, m, k);

	ofstream g("kfib.out");
	g << res[1][0] << endl;
	g.close();
}