#include <fstream>
#include <cstring>
#define r 666013

using namespace std;

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

void patrat();
void rest();

long long n, F[3][3], R[3][3], init[3][3];

int main()
{
	fin >> n;

	F[1][2] = 1;
	F[2][1] = 1;
	F[2][2] = 1;
	R[1][1] = R[2][2] = 1;
	memcpy(init, F, sizeof(F));
	while (n)
	{
		if (n % 2)
		{
			rest();
			n--;
		}
		else
		{
			patrat();
			n /= 2;
		}
	}
	fout << R[1][2];
	return 0;
}

void patrat()
{
	long long i, j, k, aux[3][3];

	memset(aux, 0, sizeof(aux));
	for (i = 1; i <= 2; i++)
		for (j = 1; j <= 2; j++)
			for (k = 1; k <= 2; k++)
				aux[i][j] = (aux[i][j] + ((F[i][k]%r) * (F[k][j]%r))%r)%r;
	memcpy(F, aux, sizeof(aux));
}

void rest()
{
	long long i, j, k, aux[3][3];

	memset(aux, 0, sizeof(aux));
	for (i = 1; i <= 2; i++)
		for (j = 1; j <= 2; j++)
			for (k = 1; k <= 2; k++)
				aux[i][j] = (aux[i][j] + ((R[i][k] % r) * (F[k][j] % r)) % r) % r;
	memcpy(R, aux, sizeof(aux));
}