#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int mod = 666013;

vector<vector<long long>> mul(vector<vector<long long>> a, vector<vector<long long>> b)
{
	int m = a.size();
	int n = b.size();
	int p = b[0].size();
	vector<vector<long long>> res(m, vector<long long>(p));
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < p; j++) {
			for (int k = 0; k < n; k++) {
				res[i][j] += a[i][k]*b[k][j];
				res[i][j] %= mod;
			}
		}
	}
	return res;
}

vector<vector<long long>> pow(vector<vector<long long>> a, int n)
{
	vector<vector<long long>> res = {{1,0},{0,1}};
	while (n) {
		if (n&1) {
			res = mul(res, a);
		}
		a = mul(a, a);
		n >>= 1;
	}
	return res;
}

int fib(int n)
{
	return pow({{0,1},{1,1}}, n)[0][1];
}

int main()
{
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);
	int n;
	cin >> n;
	printf("%d\n", fib(n));
	return 0;
}