using namespace std;
#include<fstream>
#include<cstring>
int N;
const int MAX_N = 100007, mod = 9999991;
int dp[2][MAX_N];
int main()
{
	int cur = 1, i, j;
	ifstream in("dirichlet.in"); ofstream out("dirichlet.out");
	in >> N;
	dp[0][0] = 1;
	for( i = 1; i <= N; ++i )
	{
		dp[cur][0] = 1;
		for( j = 1; j <= i; ++j )
		{
			dp[cur][j] = (1LL*(1LL * dp[cur][j-1] + 1LL * dp[1-cur][j])) % mod;
		}
		cur = 1 - cur;
	}
	out << dp[1-cur][N] % mod << "\n";
	return 0;
}