#include <iostream>
#include <fstream>

using namespace std;

int main()
{
	const int mod = 666013;
	int n, Z[2][2], Z_2[2][2], Z_T[2][2];

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

	in >> n;

	Z[0][0] = Z_2[0][0] = 0;
	Z[0][1] = Z_2[0][1] = 1;
	Z[1][0] = Z_2[1][0] = 1;
	Z[1][1] = Z_2[1][1] = 1;

	for (int i = 1; i < n - 1; i++)
	{
		Z_T[0][0] = (Z_2[0][0] * Z[0][0] + Z_2[0][1] * Z[1][0]) % mod;
		Z_T[0][1] = (Z_2[0][0] * Z[0][1] + Z_2[0][1] * Z[1][1]) % mod;
		Z_T[1][0] = (Z_2[1][0] * Z[0][0] + Z_2[1][1] * Z[1][0]) % mod;
		Z_T[1][1] = (Z_2[1][0] * Z[0][1] + Z_2[1][1] * Z[1][1]) % mod;

		Z_2[0][0] = Z_T[0][0];
		Z_2[0][1] = Z_T[0][1];
		Z_2[1][0] = Z_T[1][0];
		Z_2[1][1] = Z_T[1][1];
	}

	out << Z_2[1][1];

	return 0;
}