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

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