#include <fstream>
#include <string.h>

#define MOD 666013

using namespace std;

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

long long n, first[2][3], cmat[3][3], powr[3][3], tmp[3][3];

int main()
{
	first[1][1] = 1;
	first[1][2] = 1;

	cmat[1][1] = 0, cmat[1][2] = 1;
	cmat[2][1] = 1, cmat[2][2] = 1;

	f >> n;
	
	powr[1][1] = 1, powr[1][2] = 0;
	powr[2][1] = 0, powr[2][2] = 1;

	int exp = n - 1;
	while (exp > 0) {
		if (exp % 2 == 1) {
			memset(tmp, 0, sizeof(tmp));
			for (int i = 1; i <= 2; i++)
				for (int j = 1; j <= 2; j++)
					for (int k = 1; k <= 2; k++)
						tmp[i][j] = (tmp[i][j] + powr[i][k] * cmat[k][j]) % MOD;
			memcpy(powr, tmp, sizeof(tmp));
		}

		memset(tmp, 0, sizeof(tmp));
		for (int i = 1; i <= 2; i++)
			for (int j = 1; j <= 2; j++)
				for (int k = 1; k <= 2; k++)
					tmp[i][j] = (tmp[i][j] + cmat[i][k] * cmat[k][j]) % MOD;
		memcpy(cmat, tmp, sizeof(tmp));

		exp /= 2;
	}

	memset(tmp, 0, sizeof(tmp));

	for (int i = 1; i <= 1; i++)
		for (int j = 1; j <= 2; j++)
			for (int k = 1; k <= 2; k++)
				tmp[i][j] = (tmp[i][j] + first[i][k] * powr[k][j]) % MOD;

	g << tmp[1][1];

	return 0;
}