#include<fstream>
using namespace std;
const int mod=9999991;
int n,i,j;
long long fact[2000005];

long long pow(long long n, int p) {
     long long rez=1;
     while (p>0) 
      if (p%2==0) { n=(n*n)%mod; p/=2; }
       else { rez=(rez*n)%mod; --p; }
      return(rez%mod);
}

long long c(int n, int k) {
    long long p1=fact[n],p2=(fact[k]*fact[n-k])%mod;
     return((p1*pow(p2,mod-2))%mod);
}

int main(void) {
    ifstream fin("dirichlet.in");
    ofstream fout("dirichlet.out");
    fin>>n;
     fact[0]=1;
      for (i=1; i<=2*n; ++i) fact[i]=(fact[i-1]*i)%mod;
     long long sol=c(2*n-1,n);
      for (i=0; i<n-1; ++i) sol=(sol-c(n+i,n)+mod)%mod;
   fout<<sol;
 return(0);
}