/*
#include <fstream>
#define MOD 666013
using namespace std;
const char iname[] = "iepuri.in";
const char oname[] = "iepuri.out";
ifstream fin(iname);
ofstream fout(oname);
int X, Y, Z, A, B, C, N, Q;
int main()
{
	while (Q--)
	{
		fin >> X >> Y >> Z >> A >> B >> C >> N;
	}
	return 0;
}
*/
#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, n, ad;
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);
	//Happy Silviu ?:)) 
	for (i = 1; i <= 2; ++i)
	{
		for (j = 1; j <= 2; ++j)
		{
			ad = 0;
			for (n = 1; n <= 2; ++n) 
				ad += 1LL * AUX[i][n] * Z[n][j];
			A[i][j] = ad % 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;
}