#include <iostream>
#include <cstdio>

using namespace std;

typedef int ll;

const ll mod = 9999991ll;
ll a [1000009];


int main () {
	ll n, i, j;
	freopen ("dirichlet.in", "rt", stdin);
	freopen ("dirichlet.out", "wt", stdout);
	cin >> n;
	a [0] = 1ll % mod;
	a [1] = a [0];
	for (i = 2; i <= n; ++ i) {
		for (j = 1; j <= n; ++ j) {
			a [j] = a [j] + a [j - 1];
			if (a [j] >= mod) {
				a [j] -= mod;
			}
		}
		for (j = n; j > i; -- j) {
			a [j] = a [j] - a [j - i - 1];
			if (a [j] < 0) {
				a [j] += mod;
			}
		}
	}
	cout << a [n] << endl;
	return 0;
}