#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

#define MOD 666013

using namespace std;

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

long long n;

struct matrice
{
	long long a, b, c, d;
};

matrice z;

matrice m(matrice p)
{
	p.a %= MOD;
	p.b %= MOD;
	p.c %= MOD;
	p.d %= MOD;
	return p;
}
struct mat
{
	long long a, b;
};
matrice inmultire(matrice a, matrice b)
{
	matrice p;
	p.a = a.a*b.a + a.b*b.c;
	p.b = a.a*b.b + a.b*b.d;
	p.c = a.c*b.a + a.d*b.c;
	p.d = a.c*b.b + a.d*b.d;
	return m(p);
}
matrice exp(matrice a, long long p)
{
	if (p == 1)
		return m(a);
	if (p % 2 == 0)
		return m(exp(inmultire(a, a), p / 2));
	else
		return m(inmultire(exp(a, p - 1), a));
}
int main()
{
	fscanf(f, "%d", &n);
	z.a = 0;
	z.b = 1;
	z.c = 1;
	z.d = 1;
	mat m;
	m.a = 1;
	m.b = 1;
	z = exp(z, n - 1);
	fprintf(g, "%d", z.d);
}