#include <fstream>

using namespace std;

ifstream f("dirichlet.in");
ofstream g("dirichlet.out");

const int MOD = 9999991;

/**
bool prim(int x)
{
    if (x <= 2)
        return x == 2;
    if (x % 2 == 0)
        return 0;
    for (int d = 3; d * d <= x; d += 2)
        if (x % d == 0)
            return 0;
    return 1;
}
*/

int powlg(int a, int p)
{
    int r = 1;
    while (p)
    {
        if (p & 1)
            r = (long long)r * a % MOD;
        a = (long long)a * a % MOD;
        p >>= 1;
    }
    return r;
}

inline int invMod(int a)
{
    return powlg(a, MOD - 2);
}

int comb(int n, int k)
{
    if (k > n - k)
        k = n - k;
    int a = 1, b = 1;
    for (int i = 1; i <= k; i++)
    {
        a = (long long)a * (n - i + 1) % MOD;
        b = (long long)b * i % MOD;
    }
    a = (long long)a * invMod(b) % MOD;
    return a;
}

inline int Catalan(int n)
{
    return (long long)comb(2 * n, n) * invMod(n + 1) % MOD;
}

int main()
{
    int N;
    f >> N;
    g << Catalan(N);

    f.close();
    g.close();
    return 0;
}