#include <fstream>
#define MOD 9999991
using namespace std;
ifstream fin("dirichlet.in");
ofstream fout("dirichlet.out");
long long n,up,fact,fact2,i,x,a,y;
long long ieuclid(long long a, long long b, long long &x, long long &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
        long long x1,y1;
        long long d=ieuclid(b,a%b,x1,y1);
        x=y1;
        y=x1-(a/b)*y1;
        return d;
}
int main(){
    fin>>n;
    up=1;
    for(i=1;i<=2*n;i++){
        up*=i;
        up%=MOD;
    }
    fact=1;
    for(i=1;i<=n;i++){
        fact*=i;
        fact%=MOD;
    }
    fact2=1;
    for(i=1;i<=n+1;i++){
        fact2*=i;
        fact2%=MOD;
    }
    a=(fact*fact2)%MOD;
    ieuclid(a,MOD,x,y);
    x%=MOD;
    if(x<0)
        x+=MOD;
    fout<<(up*x)%MOD;
    return 0;
}