#include <bits/stdc++.h>
#define int long long

using namespace std;

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

const int MOD = 666013;

pair<int, int> fib(int n) {
	if(n == 0) {
		return {0, 1};
	}

	pair<int, int> p = fib(n >> 1);

	int p1 = p.first * (2 * p.second - p.first) % MOD;
	int p2 = p.first * p.first % MOD + p.second * p.second % MOD;
	if(p2 >= MOD) {
		p2 -= MOD;
	}

	if(n & 1) {
		int k = p1 + p2;

		if(k >= MOD) {
			k -= MOD;
		}

		return {p2, k};
	} else {

		return {p1, p2};
	}
}

signed main() {
	int n;
	fin >> n;

	fout << fib(n).first << '\n';
	return 0;
}