#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) % MOD;
	
	if(n & 1) {
		return {p2, (p1 + p2) % MOD};
	} else {
		return {p1, p2};
	}
}

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

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