#include <stdio.h>
#include <stdlib.h>

#define N 666013

long long **inmultire(long long **a, long long **b)
{
	long long **r = (long long **)malloc(sizeof(long long *) * 2);
	r[0] = (long long *)malloc(sizeof(long long) * 2);
	r[1] = (long long *)malloc(sizeof(long long) * 2);
	r[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % N;
	r[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % N;
	r[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % N;
	r[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % N;
	return r;
}

long long **putere(long long **m, int p)
{
	long long **r;
	if (p == 0)
	{
		long long **I = (long long **)malloc(sizeof(long long *) * 2);
		I[0] = (long long *)malloc(sizeof(long long) * 2);
		I[1] = (long long *)malloc(sizeof(long long) * 2);
		I[0][0] = I[1][1] = 1;
		I[0][1] = I[1][0] = 0;
		return I;
	}
	else
	{
		if (p % 2 == 1)
		{
			r = putere(m, (p - 1) / 2);
			return inmultire(m, inmultire(r, r));
		}
		else
		{
			r = putere(m, p / 2);
			return inmultire(r, r);
		}
	}
}

int main()
{
	int k;
	long long **m;
	FILE *f, *g;

	f = fopen("kfib.in", "r");
	g = fopen("kfib.out", "w");

	fscanf(f, "%d", &k);

	m = (long long **)malloc(sizeof(long long *) * 2);
	m[0] = (long long *)malloc(sizeof(long long) * 2);
	m[1] = (long long *)malloc(sizeof(long long) * 2);
	m[0][0] = 0;
	m[0][1] = m[1][0] = m[1][1] = 1;

	m = putere(m, k - 1);

	fprintf(g, "%lld\n", m[1][1] % N);		

	fclose(f);
	fclose(g);

	return 0;
}