#include<stdio.h>

const long long MOD = 9999991;

long long lgPow (long long a, long long p)
{
    if(p == 0) return 1;
    if(p % 2 == 1)
        return (lgPow(a,p - 1) * a) % MOD;

    long long half = (lgPow(a, p / 2)) % MOD;
    return (half * half) % MOD;
}

int main ()
{
    freopen("dirichlet.in","r",stdin);
    freopen("dirichlet.out","w",stdout);

    int n,i;
    long long sol, pmod;

    scanf("%d",&n);

    sol = 2 * n;
    pmod = 1;
    for(i = 2; i <= n; i++)
    {
        sol = (sol * (2 * n - i + 1)) % MOD;
        pmod = (pmod * i) % MOD;
    }

    sol = (sol * lgPow(pmod,MOD - 2)) % MOD;

    pmod = lgPow(n + 1, MOD - 2);
    sol = (sol * pmod) % MOD;
    printf("%lld\n",sol);
    return 0;
}