#include <fstream>

#define MOD 666013

struct Mat4
{
	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) % MOD + (m1.b * m2.c) % MOD) % MOD;
	m.b = ((m1.a * m2.b) % MOD + (m1.b * m2.d) % MOD) % MOD;
	m.c = ((m1.c * m2.a) % MOD + (m1.d * m2.c) % MOD) % MOD;
	m.d = ((m1.c * m2.b) % MOD + (m1.d * m2.d) % MOD) % MOD;
	return m;
}

int Kfib(unsigned 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()
{
	unsigned int k;
	std::ifstream fin("kfib.in");
	std::ofstream fout("kfib.out");

	fin >> k;

	int rez = Kfib(k);

	fout << rez;

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