#include <fstream>

#define MOD 666013

struct Mat4
{
	long long a, b,
	    c, d;
	Mat4() : a(1), b(0), c(0), d(1) {}
	Mat4(int a, int b, int c, int d):a(a), b(b), c(c), d(d) {}
	Mat4(const Mat4& other):a(other.a), b(other.b), c(other.c), d(other.c) {}
};

Mat4 operator *(const Mat4 &m1, const Mat4& m2)
{
	Mat4 m;
	m.a = (m1.a * m2.a + m1.b * m2.c ) % MOD;
	m.b = (m1.a * m2.b + m1.b * m2.d ) % MOD;
	m.c = (m1.c * m2.a + m1.d * m2.c ) % MOD;
	m.d = (m1.c * m2.b + m1.d * m2.d ) % MOD;
	return m;
}

long long Kfib(long long intk)
{
	Mat4 fib;
	Mat4 patrat(0, 1, 1, 1);
	while (intk)
	{
		if (intk & 1)
			fib = fib * patrat;
		patrat = patrat * patrat;
		intk >>= 1;
	}
	return fib.c;
}

int main()
{
	long long k;
	std::ifstream fin("kfib.in");
	std::ofstream fout("kfib.out");

	fin >> k;

	long long rez = Kfib(k);

	fout << rez;

	fin.close();
	fout.close();
	return 0;
}