#include <fstream>
using namespace std;

class Matrix
{
	long long v[3][3];

public:
	long long* operator[] (int idx)
	{
		return v[idx];
	}
	Matrix operator* (Matrix rhs)
	{
		const int kMod = 666013;
		Matrix p;
		p[1][1] = (((v[1][1] * rhs[1][1]) % kMod) + (v[1][2] * rhs[2][1]) % kMod) % kMod;
		p[1][2] = (((v[1][1] * rhs[1][2]) % kMod) + (v[1][2] * rhs[2][2]) % kMod) % kMod;
		p[2][1] = (((v[2][1] * rhs[1][1]) % kMod) + (v[2][2] * rhs[2][1]) % kMod) % kMod;
		p[2][2] = (((v[2][1] * rhs[1][2]) % kMod) + (v[2][2] * rhs[2][2]) % kMod) % kMod;
		return p;
	}
};

Matrix mpower(Matrix& base, int exponent)
{
	if (exponent == 1)
		return base;
	
	Matrix square = base * base;
	if (exponent % 2 == 0)
		return mpower(square, exponent / 2);
	else
		return base * mpower(square, exponent / 2);
}


int main()
{
	ifstream fin("kfib.in");
	int n = 0;
	fin >> n;
	fin.close();
	
	Matrix unit;
	unit[1][1] = unit[1][2] = unit[2][1] = 1;
	unit[2][2] = 0;

	Matrix fib;
	fib[1][1] = 1;
	fib[1][2] = fib[2][1] = fib[2][2] = 0;

	Matrix fibn = fib * mpower(unit, n - 1);
	
	ofstream fout("kfib.out");
	fout << fibn[1][1] << '\n';
	fout.close();
	return 0;
}