# include <fstream>
# define mod 9999991
using namespace std;
ifstream f ("dirichlet.in");
ofstream g ("dirichlet.out");
long long int a[1000005],s[1000005],n,i,j;
int main ()
{
	f>>n;
	a[1]=1;
	s[1]=1;
	for (i=2;i<=n;i++)
	{
		a[i]=2*a[i-1];
		a[i]=a[i]%mod;
		for (j=1;j<=i-2;j++)
		{
			a[i]+=s[j];
			a[i]=a[i]%mod;
		}
		
		s[i]=s[i-1]+a[i];
		s[i]=s[i]%mod;
	}

	g<<a[n]%mod;
return 0;
}