#include <fstream>
using namespace std;

int ** p(int ** v, int n, int put, int mod) {
	if (put == 0) {
		int ** r = new int*[n];
		for (int i = 0; i < n; i++) {
			r[i] = new int[n];
			for (int j = 0; j < n; j++) {
				if (i == j)
					r[i][j] = 1;
				else
					r[i][j] = 0;
			}
		}
		return r;
	}
	int ** q = p(v, n, put / 2, mod);
	int ** r = new int*[n];
	for (int i = 0; i < n; i++) {
		r[i] = new int[n];
		for (int j = 0; j < n; j++) {
			r[i][j] = 0;
			for (int z = 0; z < n; z++)
				r[i][j] = 1ll * (1ll * r[i][j] + 1ll * q[i][z] * q[z][j]) % (1ll * mod);
		}
	}
	if (put & 1) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				q[i][j] = 0;
				for (int z = 0; z < n; z++)
					q[i][j] = 1ll * (1ll * q[i][j] + 1ll * r[i][z] * v[z][j]) % (1ll * mod);
			}
		}
		return q;
	}
	return r;
}


int main()
{
	int ** m = new int*[2];
	ifstream in("kfib.in");
	int k;
	in >> k;
	for (int i = 0; i < 2; i++) {
		m[i] = new int[2];
	}
	m[0][0] = 0;
	m[0][1] = m[1][0] = m[1][1] = 1;
	m = p(m, 2, k, 666013);

	ofstream out("kfib.out");
	out << m[0][1];

	out.close();
	in.close();
	return 0;
}