#include <fstream>
#define MAXN 1000010
#define M 9999991
using namespace std;
long long a0[MAXN], a1[MAXN];
long n, i, j;
int main()
{
	ifstream fin("dirichlet.in");
  ofstream fout("dirichlet.out");
	fin>>n;
	for (i=1;i<=n; i++)
	{
		a1[1]=i;
		for (j=2; j<=i; j++)
			a1[j]=(a0[j]+a1[j-1])%M;
		for (j=1; j<=i; j++)
			a0[j]=a1[j];
	}//for i
	fout<<a1[n-1]<<"\n";
	return 0;
}//main