#include <iostream>
#include <fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

#define mod %666013
#define ull unsigned long long

ull k, M[2][2], F[2][2];

void multiplyMat(ull X[2][2], ull Y[2][2]) {
	ull rez[2][2];
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			rez[i][j] = ((1LL * X[i][0] * Y[0][j]) mod + (1LL * X[i][1] * Y[j][1]) mod) mod;
		}
	}
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++) X[i][j] = rez[i][j] mod;
}

void powerRaise() {
	for (int i = 0; (1 << i) <= k; i++)
	{
		if ((1 << i) & (k - 1)) {
			multiplyMat(F, M);
		}
		multiplyMat(M, M);
	}
}

int main() {
	f >> k;
	F[0][0] = F[1][1] = 1;
	M[0][1] = M[1][0] = M[1][1] = 1;
	powerRaise();
	g << F[1][1];
}