#include<cstdio>
#include<vector>
#define MOD 9999991
using namespace std;
long long n;
void read() {
	scanf("%lld",&n);   //16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640
}

void rez() {
	long long i,j;
	long long cat1=1,cat2;
	vector <long> cat;
	cat.push_back(1);
	cat.push_back(1);
	for (i=2;i<=n;i++) {
		cat[i]=0;
		for (j=0;j<i;j++)
			cat[i]=(cat[i]+(long long)cat[j]*cat[i-j-1])%MOD;
	}
	printf("%lld",cat[n]);
}

int main() {
	
	freopen("dirichlet.in","r",stdin);
	freopen("dirichlet.out","w",stdout);
	
	read();
	rez();
	return 0;
}