#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

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

#define nmax 1000005
#define MOD 9999991
#define ll long long

int n, dp[2][nmax];

void citeste(){

    f >> n;

}

void rezolva(){

    //fac un dp[i][j] = in cate moduri pot pune bilele in primele i cutii stiind ca pana acum am puse j bile si in ultima cutie pun j-k bile(k = 0,j)
    //tin doar ultimele 2 linii si recutenta o reduc la dp[linie][j] = dp[1-linie][j] + dp[linie][j-1];

    int linie = 1;
    dp[1-linie][0] = 1; dp[1-linie][1] = 1;

    for(int i=2; i<=n; ++i){
        for(int j=0; j<=i; ++j){
            if (j!=0) dp[linie][j] = (dp[1-linie][j] + dp[linie][j-1]) % MOD;
                 else dp[linie][j] = dp[1-linie][j];
        }
        linie = 1 - linie;
    }

    g << dp[1-linie][n] << "\n";

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}