#include <bits/stdc++.h>

using namespace std;

const int mod = 666013;

ifstream f("kfib.in");
ofstream g("kfib.out");

struct matrice {
	long long a, b, c, d;
	matrice() {
		a = 0;
		b = 1;
		c = 1;
		d = 1;
	}
}el_nul;


matrice produs(matrice A, matrice B)
{
	matrice sol;
	sol.a = (A.a * B.a + A.b * B.c) % mod;
	sol.b = (A.a * B.b + A.b * B.d) % mod;
	sol.c = (A.c * B.a + A.d * B.c) % mod;
	sol.d = (A.c * B.b + A.d * B.d) % mod;

	return sol;
}

matrice putere(matrice A, long long n)
{
	if(n == 0)
		return el_nul;
	if(n == 1)
		return A;
	if(n%2 == 0) {
		return putere(produs(A, A), n / 2);
	}
	else {
		return produs(A, putere(produs(A, A), n / 2));
	}
}
int main()
{
	long long k;
	f >> k;

	matrice solutie = putere(el_nul, k - 1);

	g << solutie.d;

	return 0;
}