#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define dbg(x) cout << #x <<": " << x << "\n";
#define sz(x) ((int)x.size())

using ll = long long;

const string fn = "kfib";
ifstream fin(fn + ".in");
ofstream fout(fn + ".out");

const int mod = 666013;

void inm(int a[2][2], int b[2][2]) {
	ll c[2][2];
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j) {
			c[i][j] = 0;
			for (int k = 0; k < 2; ++k)
				c[i][j] += 1LL * a[i][k] * b[k][j];
		}
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			c[i][j] %= mod;
	for (int i = 0 ; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			a[i][j] = c[i][j];
}

void expp(int a[2][2], int x[2][2], int n) {
	while (n) {
		if (n & 1)
			inm(a, x);
		inm(x, x);
		n >>= 1;
	}
}

int main() {
	int n;
	fin >> n;
	int a[2][2], ans[2][2];
	ans[0][0] = ans[0][1] = 1;

	a[0][0] = 0;
	a[0][1] = a[1][0] = a[1][1] = 1;

	expp(ans, a, n - 1);
	fout << ans[0][0];

	return 0;
}