#include <fstream>
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
const long long mod = 666013;
struct mat
{
	long long a11, a12, a21, a22;
};
mat I2 = { 1,0,0,1 };
mat fib = { 0,1,1,1 };
mat inm_mat(mat x, mat y)
{
	long long a = ((x.a11 * y.a11)%mod + (x.a12 * y.a21)%mod)%mod;
	long long b = ((x.a11 * y.a12)%mod + (x.a12 * y.a22)%mod)%mod;
	long long c = ((x.a21 * y.a11)%mod + (x.a22 * y.a21)%mod)%mod;
	long long d = ((x.a21 * y.a12)%mod + (x.a22 * y.a22)%mod)%mod;
	return { a,b,c,d };
}
mat exp_mat(mat baza, long long exp)
{
	if (exp == 0)
		return I2;
	if (exp % 2 == 0)
	{
		mat k = exp_mat(baza, exp / 2);
		return inm_mat(k, k);
	}
	return inm_mat(fib, exp_mat(baza, exp - 1));
}

int main()
{
	long long k;
	cin >> k;
	if (k == 0)
		cout << 0;
	else if (k == 1)
		cout << 1;
	else
	{
		mat q = exp_mat(fib, k-1);
		cout << q.a22;
	}

	return 0;
}