#include <stdio.h>
#include <string.h>

long long mod, last[3][3], now[3][3], A[3][3];

void inm(long long A[3][3], long long B[3][3], long long C[3][3]) //C = A * B
{
	int i, j, k;
	
	for (i = 1; i <= 2; i ++)
		for (j = 1; j <= 2; j ++)
		{
			C[i][j] = 0;
			for (k = 1; k <= 2; k ++)
				C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
		}
}

void BuildMatrix(long long N)
{
	if (N == 1)
	{
		memcpy(last, A, sizeof(last));
		return ;
	}
	
	BuildMatrix(N / 2);
	if (N % 2 == 0)
	{
		inm(last, last, now);
		memcpy(last, now, sizeof(last));
	}
	else
	{
		inm(last, last, now);
		memcpy(last, now, sizeof(last));
		inm(last, A, now);
		memcpy(last, now, sizeof(last));
	}
}

int main()
{
	long long N;
	
	freopen("kfib.in", "r", stdin);
	freopen("kfib", "w", stdout);
	
	while (scanf("%lld", &N) != EOF)
	{
		mod = 666013;
		if (N == 0)
		{
			printf("0");
			continue;
		}
		if (N == 1 || N == 2)
		{
			printf("1");
			continue;
		}
		
		A[1][1] = A[1][2] = A[2][1] = 1; A[2][2] = 0;
		BuildMatrix(N - 2);
		
		printf("%lld\n", (last[1][1] + last[1][2]) % mod);
	}
	
	return 0;
}