#include<fstream> 
#define Nmax 1000001
#define MOD 9999991
using namespace std; 
ifstream in("dirichlet.in"); 
ofstream out("dirichlet.out"); 

int st[Nmax],n,contor=0,sum[Nmax];	

int valid(int p) 
{
	int ok=1,suma;
	for(int i=1;i<=p;i++) 
		{suma=0;
			for(int j=1;j<=i;j++) 
			suma+=st[j];
			sum[i]=suma;
		}
		for(int i=1;i<=p;i++) 
			if(sum[i]>i) 
				ok=0;
	return ok;
}
void back(int p) 
{int suma;
	for(int i=0;i<=n;i++) 
		{
			st[p]=i; 
	if(valid(p))
	
			if(p==n) 
			{ suma=0;
				for(int j=1;j<=n;j++) 
                    suma+=st[j]; 
				if(suma==n) contor++; 
			}
		else back(p+1); 
	}
}
int main() 
{
	in>>n; 
	back(1);
	out<<contor%MOD;
	return 0;
}