#include <stdio.h>
#define MOD 666013

FILE *fin = fopen("kfib.in", "rt");
FILE *fout = fopen("kfib.out", "wt");

long long int n, m;

typedef struct mat
{
	long long a, b, c;
} mat;

mat getPow(long long int p)
{
	mat rez;
	if (p <= 1)
	{
		rez.a = rez.b = 1;
		rez.c = 0;
		return rez;
	}
	mat m = getPow(p / 2);
	rez.a = m.a * m.a + m.b * m.b;
	rez.b = m.a * m.b + m.b * m.c;
	rez.c = m.b * m.b + m.c * m.c;

	if (p % 2)
	{
		rez.a += rez.b;
		rez.b = rez.a - rez.b;
		rez.c = rez.b - rez.c;
	}
	rez.a %= MOD;
	rez.b %= MOD;
	rez.c %= MOD;
	return rez;
}

long long fib(long long i)
{
	if (i == 0) return 0;
	mat m = getPow(i);
	return m.b;
}

long long gcd(long long n, long long m)
{
	if (n % m == 0) return m;
	return gcd(m, n % m);
}

int main()
{
	fscanf(fin, "%I64d", &n);

	fprintf(fout, "%I64d\n", fib(n));

	fclose(fin);
	fclose(fout);
	return 0;
}