#include <iostream>
#include <fstream>

using namespace std;

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

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

	in >> n;

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

	p = n - 1;

	A[0][0] = 0;
	A[0][1] = 1;
	A[1][0] = 1;
	A[1][1] = 1;

	SOL[0][0] = 1;
	SOL[0][1] = 0;
	SOL[1][0] = 0;
	SOL[1][1] = 1;

	for (int i = 0; (1 << i) <= p; ++i)
	{
		if (((1 << i) & p))
		{
			// SOL = ( SOL * A ) % mod

			SOL_TEMP[0][0] = ((SOL[0][0] * A[0][0]) % mod + (SOL[0][1] * A[1][0]) % mod) % mod;
			SOL_TEMP[0][1] = ((SOL[0][0] * A[0][1]) % mod + (SOL[0][1] * A[1][1]) % mod) % mod;
			SOL_TEMP[1][0] = ((SOL[1][0] * A[0][0]) % mod + (SOL[1][1] * A[1][0]) % mod) % mod;
			SOL_TEMP[1][1] = ((SOL[1][0] * A[0][1]) % mod + (SOL[1][1] * A[1][1]) % mod) % mod;

			SOL[0][0] = SOL_TEMP[0][0];
			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[0][0] = ((A[0][0] * A[0][0]) % mod + (A[0][1] * A[1][0]) % mod) % mod;
		A[0][1] = ((A[0][0] * A[0][1]) % mod + (A[0][1] * A[1][1]) % mod) % mod;
		A[1][0] = ((A[1][0] * A[0][0]) % mod + (A[1][1] * A[1][0]) % mod) % mod;
		A[1][1] = ((A[1][0] * A[0][1]) % mod + (A[1][1] * A[1][1]) % mod) % mod;
	}

	out << SOL[1][1];

	return 0;
}