#include <cstdio>
#include <vector>

using namespace std;

#define file_in "dirichlet.in"
#define file_out "dirichlet.out"

#define mod 9999991

vector<long long> C;
long long n,s,res,i,k,j;

    

int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%lld", &n);
	C.push_back(1);
	for (i=1;i<=n;++i){
	     k=0;
		 for (j=0;j<i;++j)
			  k=(k+C[j]*C[i-1-j])%mod;
		 C.push_back(k);
	}
	
	printf("%lld\n", C[n]);
	
	return 0;
	
}