#include <fstream>

using namespace std;

const int MOD = 666013;
int k;
int a[3][3], b[3][3];

void MatrixProduct(int x[3][3], int y[3][3])
{
	int aux[3][3];
	long long s;
	for (int i = 1;i <= 2;++i)
		for (int j = 1;j <= 2;++j)
		{
			s = 0;
			for (int k = 1;k <= 2;++k)
				s = (1LL * s + 1LL * x[i][k] * y[k][j]) % MOD;
			aux[i][j] = s;
		}
	for (int i = 1;i <= 2;++i)
		for (int j = 1;j <= 2;++j)
			x[i][j] = aux[i][j];
}

void lgput(int exp)
{
	int unit[3][3];
	unit[1][1] = unit[2][2] = 1;
	unit[1][2] = unit[2][1] = 0;
	while (exp > 0)
	{
		if (exp % 2)
			MatrixProduct(unit, a);
		exp /= 2;
		MatrixProduct(a, a);
	}
	for (int i = 1;i <= 2;++i)
		for (int j = 1;j <= 2;++j)
			a[i][j] = unit[i][j];
}

int main()
{
	ifstream fin("kfib.in");
	ofstream fout("kfib.out");
	fin >> k;
	a[1][2] = a[2][1] = a[2][2] = 1;
	lgput(k - 1);
	b[1][2] = 1;
	MatrixProduct(b, a);
	fout << b[1][2] << "\n";
	fin.close();
	fout.close();
	return 0;
}