#include <iostream>
using namespace std;
const int mod = 666013;

struct M2
{
	long long a, b, c, d;

	M2() { a=b=c=d = 0; }

	M2(int A,int B,int C,int D)
	{
		a = A;
		b = B;
		c = C;
		d = D;
	}

	M2 operator*(const M2& m)
	{
		M2 res;
		res.a = (a * m.a + b * m.c) % mod;
		res.b = (a * m.b + b * m.d) % mod;
		res.c = (c * m.a + d * m.c) % mod;
		res.d = (c * m.b + d * m.d) % mod;
		return res;
	}

	M2 pow(int p)
	{
		if(p == 0)
			return M2(1,0,0,1);
		if(p==1)
			return *this;

		M2 P = this->pow(p >> 1);
		P = P * P;

		if(p & 1)
			P = P * (*this);

		return P;
	}
};

M2 M(0, 1, 1, 1);

int main()
{
	int n;
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);
	cin >> n;
	M2 R = M.pow(n);
	cout << R.c << endl;
	return 0;
}