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

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