#include <cstdio>
#include <cstring>

#define MODVAL 666013

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

void mul12_22(unsigned long long a[1][2], unsigned long long b[1][2], unsigned long long res[1][2])
{
	res[0][0] = ((a[0][0] * b[0][0]) % MODVAL) + ((a[0][1] * b[1][0]) % MODVAL);
	res[0][1] = ((a[0][0] * b[0][1]) % MODVAL) + ((a[0][1] * b[1][1]) % MODVAL);
}

void mul22_22(unsigned long long a[2][2], unsigned long long b[2][2], unsigned long long res[2][2])
{
	res[0][0] = ((a[0][0] * b[0][0]) % MODVAL) + ((a[0][1] * b[1][0]) % MODVAL);
	res[0][1] = ((a[0][0] * b[0][1]) % MODVAL) + ((a[0][1] * b[1][1]) % MODVAL);
	res[1][0] = ((a[1][0] * b[0][0]) % MODVAL) + ((a[1][1] * b[1][0]) % MODVAL);
	res[1][1] = ((a[1][0] * b[0][1]) % MODVAL) + ((a[1][1] * b[1][1]) % MODVAL);
}

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

	if (p == 1) {
		memcpy(res, z, 4 * sizeof(unsigned long long));
		return;
	}
	
	power(z, r1, p / 2);

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

int main()
{
	unsigned long long k;
	unsigned long long r1[2][2];
	unsigned long long r2[1][2];


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

	scanf("%llu", &k);

	if (k == 0) {
		printf("%llu\n", 0ull);
		return 0;
	}

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

	power(z, r1, k - 1);
	mul12_22(m1, r1, r2);

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

	return 0;
}