#include <fstream>
#include <cstring>
#define MOD 666013
#define LL long long
using namespace std;
const char iname[] = "kfib.in";
const char oname[] = "kfib.out";
ifstream fin(iname);
ofstream fout(oname);
LL k, i, j;
LL X[3][3], Z[3][3], AUX[3][3];
LL ANS[3][3];
void mul(LL A[3][3], LL B[3][3])
{
	memcpy (Z, B, sizeof(LL) * 3 * 3);
	memcpy (AUX, A, sizeof(LL) * 3 * 3);
	/*
	A[1][1] = ((AUX[1][1] * Z[1][1]) % MOD + (AUX[1][2] * Z[2][1]) % MOD) % MOD;
	A[1][2] = ((AUX[1][1] * Z[1][2]) % MOD + (AUX[1][2] * Z[2][2]) % MOD) % MOD;
	A[2][1] = ((AUX[2][1] * Z[1][1]) % MOD + (AUX[2][2] * Z[2][1]) % MOD) % MOD;
	A[2][2] = ((AUX[2][1] * Z[1][2]) % MOD + (AUX[2][2] * Z[2][2]) % MOD) % MOD;
	*/
	for (i = 1; i <= 2; ++i)
		for (j = 1; j <= 2; ++j)
			A[i][j] = ((AUX[i][1] * Z[1][j]) % MOD + (AUX[i][2] * Z[2][j]) % MOD) % MOD;
}
int main()
{
	fin >> k;
	for (i = 1; i <= 2; ++i) for (j = 1; j <= 2; ++j) X[i][j] = 1;
	X[1][1] = 0;  ANS[1][1] = ANS[2][2] = 1;
	k -= 1;
	for (;k > 0; k /= 2)
	{
		if (k % 2 == 1) mul(ANS, X);
		mul(X, X);
	}
	fout << ANS[2][2] << '\n';
	return 0;
}