#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>

using namespace std;
//ifstream cin("/Users/alekuw/Desktop/informatica/informatica/Products/Debug/date.in");
//ofstream cout("/Users/alekuw/Desktop/informatica/informatica/Products/Debug/date.out");
ifstream cin("dirichlet.in");
ofstream cout("dirichlet.out");
int n;
const int MOD=9999991;
const int NMAX=1000005;
long long cata[NMAX];

int main() {
    cin>>n;
    cata[0]=cata[1]=1;
    for(int i=2;i<=n;++i){
        for(int j=0;j<i;j++){
            cata[i]+=(cata[j]*cata[i-j-1])%MOD;
            if(cata[i]>=MOD) cata[i]-=MOD;
        }
    }
    cout<<cata[n];
    return 0;
}