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

using ll = long long;

constexpr ll mod = 9999991;

ll factorial(const ll lim){
	ll rez = 1;
	for(ll i = lim; i > 1; --i){
		rez *= i;
		rez %= mod; }
	return rez; }

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 = factorial(2*n);
	rez *= inv_mod(factorial(n+1));
	rez %= mod;
	rez *= inv_mod(factorial(n));
	rez %= mod;
	return rez; }

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