#include <iostream>
#include <fstream>

using namespace std;

const int M = 666013;
const int N = 2;

void produs(int p[2][2], int a[2][2])
{
	int aux[2][2];

	for (int i = 0; i < 2; i++)
	{
		for (int j = 0; j < 2; j++)
		{
			aux[i][j] = 0;

			for (int k = 0; k < 2; k++)
			{
				aux[i][j] += (long long)p[i][k] * a[k][j] % M;
				aux[i][j] %= M;
			}
		}
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			p[i][j] = aux[i][j];
		}
	}
}

int fibo(int n)
{
	int a[2][2] = { (1, 1), (1, 0) };
	int p[2][2] = { (1, 0), (0, 1) };
	n--;

	while (n != 0)
	{
		int cifb = n % 2;

		if (cifb != 0)
		{
			produs(p, a);
		}
		produs(a, a);
		n = n / 2;
	}

	return p[0][0];
}

int main()
{
	ifstream in("kfib.in");
	ofstream out("kfib.out");

	int k;
	in >> k;
	out << fibo(k);

	in.close();
	out.close();

	return 0;
}