#include <cstdio>
#include <cstring>
#define maxn 4
#define mod 666013

using namespace std;

int Rmat[maxn][maxn], Cmat[maxn][maxn], Fmat[maxn][maxn];
int K;
void mul (int A[][maxn], int B[][maxn])
{	
	int AUX[maxn][maxn], i , j, k;
	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] + 1LL * A[i][k] * B[k][j]) % mod;
	memcpy (A, AUX, sizeof (AUX));
}

int main ()
{
	freopen ("kfib.in", "r", stdin);
	freopen ("kfib.out", "w", stdout);
	scanf ("%d", &K);
	Rmat[1][1] = Rmat[2][2] = 1;
	Cmat[2][1] = Cmat[1][2] = Cmat[2][2] = 1;
	Fmat[1][1] = 1;Fmat[1][2] = 0;
	while (K > 0)
	{
		if (K & 1)
			mul (Rmat, Cmat);
		mul (Cmat, Cmat);
		K >>= 1;
	}
	mul (Fmat, Rmat);
	printf ("%d\n", Fmat[1][2]);
	return 0;
}