#include <fstream>
using namespace std;

namespace e_043_fibonacci
{
	typedef unsigned long long uint64;

	template <typename T>
	class mat2
	{
	private:
		T a, b, c, d;
	public:
		mat2(T a, T b, T c, T d) : a(a), b(b), c(c), d(d) {}

		mat2(const mat2<T>& m) : a(m.a), b(m.b), c(m.c), d(m.d) {}

		mat2<T>& operator *= (const mat2<T>& m)
		{
			mat2 res(a*m.a + b*m.c, a*m.b + b*m.d, c*m.a + d*m.c, c*m.b + d*m.d);
			(*this) = res;
			return *this;
		}

		mat2<T> operator * (const mat2<T>& m)
		{
			mat2 c = *this;
			c *= m;
			return c;
		}

		mat2<T>& operator %= (const uint64 mod)
		{
			a %= mod; b %= mod; c %= mod; d %= mod;
			return *this;
		}

		mat2<T> operator % (const uint64 mod) const
		{
			mat2 res = *this;
			res %= mod;
			return res;
		}

		T& operator () (int i, int j)
		{
			if (i == 0 && j == 0) return a;
			if (i == 0 && j == 1) return b;
			if (i == 1 && j == 0) return c;
			if (i == 1 && j == 1) return d;

			return a; //index out of bounds exception should be thrown
		}
	};

	mat2<uint64> compute_fib_pow_mod(const mat2<uint64>& A, uint64 p, uint64 mod)
	{
		if (p == 0) return mat2<uint64>(1, 0, 0, 1); //identity	
		if (p == 1) return A % mod;
		//otherwise
		mat2<uint64> Ap = A % mod;
		uint64 k = 1;
		while (2 * k <= p) { Ap *= Ap; Ap %= mod; k = 2 * k; }

		mat2<uint64> Apmk = compute_fib_pow_mod(A, p - k, mod);
		Ap *= Apmk;

		Ap %= mod;

		return Ap;
	}

}

int main()
{
	using namespace e_043_fibonacci;

	string in_file = "kfib.in";
	string out_file = "kfib.out";

	uint64 mod = 666013;

	uint64 K;

	ifstream ifs(in_file);
	ifs >> K;
	ifs.close();

	mat2<uint64> A(1, 1, 1, 0);
	mat2<uint64> AK1 = compute_fib_pow_mod(A, K - 1, mod);

	uint64 FK = AK1(0, 0);

	ofstream ofs(out_file);
	ofs << FK;
	ofs.close();

	return 0;
}

int e_043_fibonacci_slow()
{
	string in_file = "kfib.in";
	string out_file = "kfib.out";

	int mod = 666013;

	int K;

	ifstream ifs(in_file);
	ifs >> K; 
	ifs.close();

	int a = 0, b = 1, c;
	for (int k = 2; k <= K; k++) {
		c = (a + b) % mod;
		a = b;
		b = c;
	}

	int FK;
	if (K == 0) FK = 0;
	if (K == 1) FK = 1;
	if (K > 1) FK = b;

	ofstream ofs(out_file);
	ofs << FK;
	ofs.close();

	return 0;
}