#include <fstream>

using namespace std;

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

const long long mod = 9999991;

long long lg_put(long long a,long long b)
{
    long long p=1;
    while(b)
    {
        if(b%2==0)
        {
            a=a*a%mod;
            b=b/2;
        }
        else
        {
            p=p*a%mod;
            b--;
        }
    }
    return p%mod;
}

int main()
{
    long long n,p1=1,p2=1,i;
    cin >> n;
    for( i = 1; i<=2*n; i++)
        p1=p1*i%mod;
    p2=n+1;
    for( i = 1; i<=n; i++)
        p2=((p2*i)%mod*i)%mod;
    cout << ( p1 * lg_put(p2, mod-2) )% mod;
    /// Catalan = ( 2 N ) ! / ( N! * (N+1)! )
    return 0;
}