/*
	http://www.infoarena.ro/problema/kfib
*/

#include <fstream>
#include <cstring>
#define MOD 666013
using namespace std;

void multiply(int A[][2], int B[][2], int C[][2])
{
	for (int i = 0; i < 2; ++i)
	{
		for (int j = 0; j < 2; ++j)
		{
			C[i][j] = 0;
			for (int k = 0; k < 2; ++k)
			{
				C[i][j] = (C[i][j] * 1LL + 1LL * A[i][k] * B[k][j]) % MOD;
			}
		}
	}
}

//void logExp()

int main(void)
{
	int k, sol;
	ifstream fin("kfib.in");
	fin >> k;
	fin.close();

	if (k == 0)
	{
		sol = 0;
	}
	else
	{
		int exp[2][2], solution[2][2], prod[2][2];
		exp[0][0] = 1; exp[0][1] = 1;
		exp[1][0] = 1; exp[1][1] = 0;

		for (int i = 0; i < 2; ++i)
			for (int j = 0; j < 2; ++j)
				prod[i][j] = (i == j);
		--k;
		while (k)
		{
			if (k & 1)
			{
				multiply(prod, exp, solution);
				memcpy(prod, solution, sizeof(solution));
			}
			multiply(exp, exp, solution);
			memcpy(exp, solution, sizeof(solution));
			k >>= 1;
		}
		sol = prod[0][0];
	}

	ofstream fout("kfib.out");
	fout << sol << "\n";
	fout.close();
	return 0;
}