#include<fstream>
#include<algorithm>
using namespace std;
const int mod=9999991;
int n,i,j,c[2000][2000],indc=1,indp;

int main(void) {
     // incerc brut sa vad daca merge formula
    ifstream fin("dirichlet.in");
    ofstream fout("dirichlet.out");
    fin>>n; c[0][0]=1;
    for (i=1; i<=2*n; ++i) {
        c[i][0]=1;
        for (j=1; j<=min(i,n+1); ++j)
         c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
         }
   int 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);
}