#include <bits/stdc++.h>

using namespace std;

const int mod = 666013;
struct matrix {
	vector<vector<int>>a;
	matrix(const vector<vector<int>>&that) {
		a = that;
	}
	matrix(int n = 0, int m = 0) {
		a.resize(n, vector<int>(m));
	}
	matrix() {};
	void unitate() {
		for (int i = 0; i < a.size(); ++i)
			a[i][i] = 1;
	}
	void operator *=(const matrix &that) {
		const auto &b = that.a;
		vector<vector<int>>aux(a.size(), vector<int>(b[0].size()));

		for (int i = 0; i < 2; ++i)
			for (int j = 0; j < 2; ++j)
				for (int k = 0; k < 2; ++k)
					aux[i][j] = (aux[i][j] + 1LL * a[i][k] * b[k][j]) % mod;

		a = aux;
	}
	void operator ^=(int p) {
		matrix result(a.size(), a[0].size());
		result.unitate();
		for(; p; p /= 2) {
			if(p % 2)
			  result *= (*this);
			*this *= (*this);
		}
		*this = result;
	}
};

int main() {
	ifstream cin("kfib.in");
	ofstream cout("kfib.out");

	int n;
	cin >> n;

	if (n <= 2) {
		if (!n)
			cout << 0;
		else cout << 1;

		return 0;
	}

	matrix fibo_init(1, 2);
	fibo_init.a[0][0] = 0, fibo_init.a[0][1] = 1;

	matrix fibo_mat(2, 2);
	fibo_mat.a[0] = {0, 1};
	fibo_mat.a[1] = {1, 1};

	fibo_mat ^= n-1;
	fibo_init *= fibo_mat;
	cout << fibo_init.a[0][1];
	return 0;
}