#include <cstdio>
#include <cstring>

#define MODVAL 666013

void mul13_33(unsigned long long a[1][3], unsigned long long b[3][3], unsigned long long res[1][3])
{
	for (int i = 0; i < 3; i++) {
		res[0][i] = 0;
		for (int j = 0; j < 3; j++) {
			res[0][i] += (a[0][j] * b[j][i]) % MODVAL;
			res[0][i] %= MODVAL;
		}
	}
}

void mul33_33(unsigned long long a[3][3], unsigned long long b[3][3], unsigned long long res[3][3])
{
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			res[i][j] = 0;
			for (int k = 0; k < 3; k++) {
				res[i][j] += (a[i][k] * b[k][j]) % MODVAL;
				res[i][j] %= MODVAL;
			}
		}
	}
}

void power(unsigned long long a[3][3], unsigned long long res[3][3], unsigned long long p)
{
	unsigned long long r1[3][3];
	unsigned long long r2[3][3];

	if (p == 1) {
		memcpy(res, a, 9 * sizeof(unsigned long long));
		return;
	}

	power(a, r1, p / 2);

	if (p % 2 == 0) {
		mul33_33(r1, r1, res);
	} else {
		mul33_33(r1, r1, r2);
		mul33_33(r2, a, res);
	}
}

int main()
{
	unsigned long long i;
	unsigned long long r1[3][3];
	unsigned long long r2[1][3];

	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);

	scanf("%llu", &i);
	if (i == 0) {
		printf("%llu\n", 0ull);
		return 0;
	}
	if (i == 1) {
		printf("%llu\n", 1ull);
		return 0;
	}

	unsigned long long z[3][3] = {
		{1, 1, 0},
		{1, 0, 0},
		{0, 0, 1}};
	unsigned long long m1[1][3] = {
		{0, 1, 1}};

	power(z, r1, i);
	mul13_33(m1, r1, r2);

	printf("%llu\n", r2[0][0]);

	return 0;
}