#include <iostream>
#include <fstream>
#define Mod 666013

using namespace std;

struct matr {
	long long A, B, C, D;
};

matr inm(const matr & b, const matr & a) {
		matr c;
		c.A = (b.A * a.A + b.B * a.C) % Mod;
		c.B = (b.A * a.B + b.B * a.D) % Mod;
		c.C = (b.C * a.A + b.D * a.C) % Mod;
		c.D = (b.C * a.B + b.D * a.D) % Mod;
		return c;
	}

int main() {
	int k, masc;
	matr a, s;
	ifstream f("kfib.in");
	ofstream g("kfib.out");
	f >> k;
	masc = 1;
	a.A = s.B = s.C = 0;
	a.B = a.C = a.D = s.A = s.D = 1;
	while (masc <= k-1) {
		if (k-1 & masc) {
			s = inm(s, a);
		}
		a = inm(a, a);
		masc = masc << 1;
	}

	g << s.D;
	f.close();
	g.close();
	return 0;
}