#include <bits/stdc++.h>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

using ll = long long;
const int kMod = 666013;

void addSelf(int &x, int y) {
	x += y;
	if(x >= kMod) {
		x -= kMod;
	}
}

int add(int x, int y) {
	addSelf(x, y);
	return x;
}

void multSelf(int &x, int y) {
	x = (ll) x * y % kMod;
}

int mult(int x, int y) {
	multSelf(x, y);
	return x;
}

vector<vector<int>> mult(const vector<vector<int>> &a, const vector<vector<int>> &b) {
	vector<vector<int>> c(a.size(), vector<int>(b.size()));
	#pragma omp parallel for private(i,j,k) shared(a,b,c)
	for(int i = 0; i < (int) a.size(); i++) {
		for(int k = 0; k < (int) a[0].size(); k++) if(a[i][k] != 0) {
			for(int j = 0; j < (int) b.size(); j++) {
				addSelf(c[i][j], mult(a[i][k], b[k][j]));
			}
		}
	}
	return c;
}

vector<vector<int>> lgpow(vector<vector<int>> a, int n) {
	vector<vector<int>> res(a.size(), vector<int>(a.size()));
	for(int i = 0; i < (int) a.size(); i++) {
		res[i][i] = 1;
	}
	while(n) {
		if(n & 1) {
			res = mult(res, a);
		}
		a = mult(a, a);
		n >>= 1;
	}
	return res;
}

int main() {
	int n;
	fin >> n;
	vector<vector<int>> fib = {
		{1, 1},
		{1, 0}
	};
	fib = lgpow(fib, n);
	fout << fib[0][1] << '\n';
	return 0;
}