#include <iostream>
#include <fstream>

using namespace std;

int main()
{
	const int mod = 666013;
	int n, p, A[2][2], A_TEMP[2][2], SOL[2][2], SOL_TEMP[2][2];

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

	in >> n;
	
	if (n == 0)				// setam valorile de start pentru un input intre 0 si 2, si anume 0, 1, 1
	{	
		out << 0;
		return 0;
	}

	if (n == 1 || n == 2)
	{
		out << 1;
		return 0;
	}

	p = n - 1;				// setam puterea la care trebuie sa calculam matricea

	A[0][0] = 0;			// setam matricea pe care calculam
	A[0][1] = 1;
	A[1][0] = 1;
	A[1][1] = 1;

	SOL[0][0] = 1;			// setam elementul neutru la inmultirea matricelor
	SOL[0][1] = 0;
	SOL[1][0] = 0;
	SOL[1][1] = 1;

	for (int i = 0; (1 << i) <= p; ++i)		// calculam A ^ p folosind ridicarea la putere in timp logaritmic cu ajutorul operatiilor pe biti
	{
		if (((1 << i) & p))
		{
			// SOL = ( SOL * A ) % mod

			SOL_TEMP[0][0] = ((1LL * SOL[0][0] * A[0][0]) % mod + (1LL * SOL[0][1] * A[1][0]) % mod) % mod;		// calculam intr-o matrice temporala
			SOL_TEMP[0][1] = ((1LL * SOL[0][0] * A[0][1]) % mod + (1LL * SOL[0][1] * A[1][1]) % mod) % mod;
			SOL_TEMP[1][0] = ((1LL * SOL[1][0] * A[0][0]) % mod + (1LL * SOL[1][1] * A[1][0]) % mod) % mod;
			SOL_TEMP[1][1] = ((1LL * SOL[1][0] * A[0][1]) % mod + (1LL * SOL[1][1] * A[1][1]) % mod) % mod;

			SOL[0][0] = SOL_TEMP[0][0];			// salvam rezultatul din matricea temporala
			SOL[0][1] = SOL_TEMP[0][1];
			SOL[1][0] = SOL_TEMP[1][0];
			SOL[1][1] = SOL_TEMP[1][1];
		}

		// A = ( A * A ) * mod

		A_TEMP[0][0] = ((1LL * A[0][0] * A[0][0]) % mod + (1LL * A[0][1] * A[1][0]) % mod) % mod;				// calculam intr-o matrice temporala
		A_TEMP[0][1] = ((1LL * A[0][0] * A[0][1]) % mod + (1LL * A[0][1] * A[1][1]) % mod) % mod;
		A_TEMP[1][0] = ((1LL * A[1][0] * A[0][0]) % mod + (1LL * A[1][1] * A[1][0]) % mod) % mod;
		A_TEMP[1][1] = ((1LL * A[1][0] * A[0][1]) % mod + (1LL * A[1][1] * A[1][1]) % mod) % mod;

		A[0][0] = A_TEMP[0][0];				// salvam rezultatul din matricea temporala
		A[0][1] = A_TEMP[0][1];
		A[1][0] = A_TEMP[1][0];
		A[1][1] = A_TEMP[1][1];
	}

	out << SOL[1][1];	// afisam solutia

	return 0;
}