//
//  main.cpp
//  Dirichlet
//
//  Created by Andrada Minca on 23.10.2025.
//

#include <fstream>
#include <vector>
using namespace std;
ifstream cin("dirichlet.in");
ofstream cout("dirichlet.out");
vector<long long> v(1000005);
int main()
{
    int n;
    cin>>n;
    v[0]=1;
    v[1]=1;
    for(int i=2;i<=n;++i)
        for(int j=0;j<i;++j)
            v[i]+=(v[j]*v[i-j-1])%9999991;
    cout<<v[n]%9999991;
    return 0;
}