#include<fstream>
using namespace std;

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

void inmulteste(long long **x, long long **y) {
	int a, b, c, d;
	a = (x[0][0] * y[0][0]) % 666013 + (x[0][1] * y[1][0]) % 666013;
	b = (x[0][0] * y[0][1]) % 666013 + (x[0][1] * y[1][1]) % 666013;
	c = (x[1][0] * y[0][0]) % 666013 + (x[1][1] * y[1][0]) % 666013;
	d = (x[1][0] * y[0][1]) % 666013 + (x[1][1] * y[1][1]) % 666013;
	x[0][0] = a % 666013;
	x[0][1] = b % 666013;
	x[1][0] = c % 666013;
	x[1][1] = d % 666013;
}

long long** ridica(long long **m, int k) {
	long long **ans = new long long*[2];
	ans[0] = new long long[2];
	ans[1] = new long long[2];
	ans[0][0] = ans[1][1] = 1;
	ans[1][0] = ans[0][1] = 0;

	while(k) {
		if(k % 2 == 1) {
			inmulteste(ans, m);
		}
		inmulteste(m, m);
		k /= 2;
	}
	return ans;
}

int main() {
	int k, ans;
	long long **a;
	fin >> k;
	a = new long long*[2];
	a[0] = new long long[2];
	a[1] = new long long[2];
	a[0][0] = a[0][1] = a[1][0] = 1;
	a[1][1] = 0;
	a = ridica(a, k-1);
	ans = a[0][0];
	fout << ans;
	return 0;
}