#include<fstream>
using namespace std;
const int mod=9999991;
int n,i;
long long p1,p2,p3,p4,p5,fact;

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);
}

int main(void) {
    ifstream fin("dirichlet.in");
    ofstream fout("dirichlet.out");
    fin>>n; fact=1;
    for (i=1; i<=2*n-1; ++i) {
        if (i-1==n-2) p5=fact;
         else if (i-1==n-1) p3=fact;
          else if (i-1==n) p2=fact;
           else if (i-1==n+1) p4=fact;
         fact=(fact*i)%mod;
           }
    p1=fact; 
     int sol=((p1*pow((p2*p3)%mod,mod-2))%mod-(p1*pow((p4*p5)%mod,mod-2))%mod+mod)%mod;
   fout<<sol;
 return(0);
}