#include <fstream>
#include <tuple>
using namespace std;

using ll = long long;

constexpr ll mod = 9999991;

tuple<ll, ll> euclid_extins(const ll a, const ll b){
	if(b == 0){
		return make_tuple(1, 0); }
	// ax + by = g
	// ax + (a/b)bx - (a/b)bx + by = g
	// (a%b)x + (y + (a/b)x)b = g
	// b(y + (a/b)x) + (a%b)x = g
	int x1, y1;
	tie(y1, x1) = euclid_extins(b, a%b);
	return make_tuple(x1, y1 - (a/b)*x1); }

ll inv_mod(const ll x){
	// rez * x = 1 + p * mod
	// rez * x - p * mod = 1
	// rez * x + (-p) * mod = 1
	return (get<0>(euclid_extins(x, mod)) + mod)%mod; }

ll catalan(const ll n){
	ll rez = 1;
	ll tmp = 1;
	for(ll i = 2; i <= n; ++i){
		tmp *= i;
		tmp %= mod; }
	rez *= inv_mod(tmp);
	// rez = 1 / n!

	tmp *= (n+1);
	rez *= inv_mod(tmp);
	rez %= mod;
	// rez = 1 / n! * (n+1)!

	for(ll i = n+2; i <= 2*n; ++i){
		tmp *= i;
		tmp %= mod; }
	rez *= tmp;
	rez %= mod;
	// rez = (2*n)! / n! * (n+1)!
	return rez; }

int main(){
	ifstream f("dirichlet.in");
	ofstream g("dirichlet.out");
	ll x;
	f >> x;
	g << catalan(x);
	return 0; }