#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#define nmax 1000005
#define mod 9999991
using namespace std;

int curent[nmax], anterior[nmax], n, i, j;
void init() {
    for(int i=0; i<=n; i++)
        curent[i] = 0, anterior[i] = 0;
    curent[0] = 1;
    curent[1] = 1;
    anterior[0] = 1;
    anterior[1] = 1;
}

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

    f>>n;

    //dp[i][j] = nr. de posibilitati de a pune j bile in primele i cutii)
    //dp[1][] se completeaza manual

    //in rest, daca ma aflu la cutia i, pot pune aici intre 0 si i bile (adica continui toate dp[i-1][0..i])
    //pe foaie, se deduce ca dp[i][j] = dp[i][j-1] + dp[i-1][j] (dinamica din stanga + dinamica de deasupra)
    //+ folosesc ultimele 2 linii ale dinamicii

    init();

    for(i=2; i<=n; i++) {
        for(j=1; j<=i; j++) curent[j] = (curent[j-1] + anterior[j]) % mod, anterior[j] = curent[j];
        //for(j=1; j<=i; j++) anterior[j] = curent[j]; //pot face si actualizarea in aceeasi bucla
    }

    //for(j=0; j<=n; j++) cout<<curent[j]<<" ";
    g<<curent[n]<<"\n";

	return 0;
}