#include <fstream>

using namespace std;

ifstream in("dirichlet.in");
ofstream out("dirichlet.out");

const int N=1000000;
const int P=9999991;
long long a[N],s[N];
int n;

int main(){
	in>>n;
	a[1]=1;
	s[1]=1;
	for(int i=2;i<=n;i++){
		a[i]=(a[i-1]%P+s[i-1]%P)%P;
		s[i]=s[i-1]+a[i];
	}
	out<<a[n]%P;
	return 0;
}