#include <fstream>

using namespace std;

#define MOD 666013

ifstream fin("kfib.in");
ofstream fout("kfib.out"); 

struct matrice
{
	int n, m;
	long long mat[3][3];
};

void inmultire_matrice(matrice &a, matrice &b)
{
	matrice rez; rez.n = 2; rez.m = 2;
	rez.mat[1][1] = (a.mat[1][1] * b.mat[1][1] + a.mat[1][2] * b.mat[2][1]) % MOD;
	rez.mat[1][2] = (a.mat[1][1] * b.mat[1][2] + a.mat[1][2] * b.mat[2][2]) % MOD;
	rez.mat[2][1] = (a.mat[2][1] * b.mat[1][1] + a.mat[2][2] * b.mat[2][1]) % MOD;
	rez.mat[2][2] = (a.mat[2][1] * b.mat[1][2] + a.mat[2][2] * b.mat[2][2]) % MOD;
	
	a = rez;
}

matrice exp_log(matrice n, int p)
{
	if (p < 2)
		return n;
	matrice rezultat = n; p--;
	while (p)
	{
		if (p % 2)
			inmultire_matrice(rezultat, n);
		inmultire_matrice(n, n);
		p /= 2;
	}
	return rezultat;
}

int fibonacci(int k)
{
	if (k <= 0)
		return 0;
	if (k == 1)
		return 1;

	matrice fib; fib.n = 1; fib.m = 2;
	fib.mat[1][1] = 0; fib.mat[1][2] = 1;

	matrice constant; constant.n = 2; constant.m = 2;
	constant.mat[1][1] = 0;
	constant.mat[1][2] = constant.mat[2][1] = constant.mat[2][2] = 1;

	matrice rez = exp_log(constant, k - 1);

	constant.mat[1][1] = (1LL * fib.mat[1][1] * rez.mat[1][1] + 1LL * fib.mat[1][2] * rez.mat[2][1]) % MOD;
	constant.mat[1][2] = (1LL * fib.mat[1][1] * rez.mat[1][2] + 1LL * fib.mat[1][2] * rez.mat[2][2]) % MOD;

	return constant.mat[1][2];
}

int main()
{
	int k; fin >> k;

	fout << fibonacci(k);
	return 0;
}