#include <fstream>
#define N 2
#define MOD 666013

using namespace std;

ifstream cin("kfib.in");
ofstream cout("kfib.out");

struct matrix
{
	int m[N][N];

	matrix operator * (matrix B)
	{
		matrix C;
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				C.m[i][j] = 0;
				for (int k = 0; k < N; ++k)
					C.m[i][j] = (C.m[i][j] + 1LL * m[i][k] * B.m[k][j]) % MOD;
			}
		}
		return C;
	}
} unit, rec, fib1;

matrix exp(matrix A, int p)
{
	matrix ans = unit;
	while (p) {
		if (p & 1)
			ans = ans * A, --p;
		else
			p >>= 1, A = A * A;
	}
	return ans;
}

void hard_copy()
{
	unit.m[0][1] = unit.m[1][0] = 0;
	unit.m[0][0] = unit.m[1][1] = 1;

	rec.m[1][1] = 0;
	rec.m[0][0] = rec.m[0][1] = rec.m[1][0] = 1;

	fib1.m[0][0] = 1;
	fib1.m[1][1] = fib1.m[0][1] = fib1.m[1][0] = 0;
}

int main()
{
	hard_copy();

	int n;
	cin >> n;

	if (n == 0)
		cout << 0;
	else if (n == 1)
		cout << 1;
	else
		cout << (exp(rec, n - 1) * fib1).m[0][0];
	return 0;
}