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

using namespace std;

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

int main() {
	int k, masc;
	matr a, s;
	fstream 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 = s * a ;
			cout << "s: \n" << s.A << " " << s.B << "\n" << s.C << " " << s.D << "\n\n";
		}
		a = a * a;
		cout << "masc= " << masc << "\n";
		cout <<"a: \n"<< a.A << " " << a.B << "\n" << a.C << " " << a.D << "\n\n";
		masc = masc << 1;
	}

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