#include <algorithm>
#include <iostream>
#include <fstream>

#define ll long long
#define restRez 9999991

using namespace std;

int n;
int p[300000];
int prim[300000];

inline void prime(int LIM)
{
	for (int i = 1; ((i * i) << 1) + (i << 1) <= LIM; i++)
		if (!(p[i >> 3] & (1 << (i & 7))))
			for (int j = ((i * i) << 1) + (i << 1); (j << 1) + 1 <= LIM; j += (i << 1) + 1)
				p[j >> 3] |= (1 << (j & 7));

	prim[++prim[0]] = 2;
	for (int i = 1; (i << 1) + 1 <= LIM; i++)
		if (!(p[i >> 3] & (1 << (i & 7))))
			prim[++prim[0]] = (i << 1) + 1;
}

int calc(int n, int x)
{
	int sol = 0;
	for (int i = x; ; )
	{
		sol += n / i;
		if (i > n / x)
			break;
		i *= x;
	}

	return sol;
}

int main()
{
	ifstream cin("dirichlet.in");
	ofstream cout("dirichlet.out");

	cin >> n;

	ll sol = 1;

	prime(1000000);
	for (int i = 1; i <= prim[0]; i++)
	{
		int a = calc(2 * n, prim[i]) - calc(n, prim[i]) - calc(n + 1, prim[i]);

		for (; a; a--)
			sol = (sol * prim[i]) % restRez;
	}

	cout << sol;

	return 0;
}