#include <fstream>



struct mat2x2
{
	long long a11, a12, a21, a22;
};



mat2x2 multiply(mat2x2 m1, mat2x2 m2)
{


	return {m1.a11 * m2.a11 + m1.a12 * m2.a21,
		m1.a11 * m2.a12 + m1.a12 * m2.a22,
		m1.a21 * m2.a11 + m1.a22 * m2.a21,
		m1.a21 * m2.a12 + m1.a22 * m2.a22};


}



mat2x2 normalize(mat2x2 in)
{

	return {in.a11 % 666013,
		in.a12 % 666013,
		in.a21 % 666013,
		in.a22 % 666013};

}


mat2x2 fast_exp(mat2x2 in, int n)
{
	if (n == 1)
		return normalize(in);
	if (n & 0x1)
		return normalize(multiply(normalize(in), normalize(fast_exp(in, n-1))));
	else
		return normalize(fast_exp(normalize(multiply(in, in)), n/2));

}


long long n;
mat2x2 z;


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

	fin>>n;
	z = {0, 1, 1, 1};
	z = fast_exp(z, n-1);
	fout << z.a22;

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