#include <bits/stdc++.h>

using namespace std;

const int mod = 666013;
long long ans[3][3], n, rez[3][3], baza[3][3];

void prod(long long m1[3][3], long long m2[3][3]) {
	for (auto& row : rez) fill(row, row + 3, 0);

	for (int i = 1; i <= 2; ++i) {
		for (int j = 1; j <= 2; ++j) {
			for (int k = 1; k <= 2; ++k) {
				rez[i][j] = (rez[i][j] + m1[i][k] * m2[k][j]) % mod;
			}
		}
	}
}

void lgpow(int e) {
	
	for (int pow = 1; pow <= e; pow <<= 1) {
		if (pow & e) {
			prod(ans, baza);
			for (int i = 1; i <= 2; ++i) for (int j = 1; j <= 2; ++j) ans[i][j] = rez[i][j];
		}
		prod(baza, baza);
		for (int i = 1; i <= 2; ++i) for (int j = 1; j <= 2; ++j) baza[i][j] = rez[i][j];
	}
	
}

int main() {
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;

	baza[1][1] = baza[1][2] = baza[2][1] = 1;
	ans[1][1] = ans[2][2] = 1;

	lgpow(n - 2);

	//for (int i = 1; i <= 2; ++i) {
	//	cout << ans[i][1] << ' ' << ans[i][2] << '\n';
	//}
	
	long long out = ans[1][1] + ans[2][1];
	out %= mod;

	cout << out;

	return 0;
}