#include <cstdio>

#define Mod 9999991
#define NMax 1000005

using namespace std;

int N, DP[2][NMax];

int main()
{
    freopen ("dirichlet.in", "r", stdin);
    freopen ("dirichlet.out", "w", stdout);
    scanf ("%d", &N);
    DP[0][0]=1;
    int l=1;
    for (int i=1; i<=N; ++i, l=1-l)
    {
        DP[l][0]=1;
        for (int j=1; j<=i; ++j)
        {
            DP[l][j]=DP[l][j-1]+DP[1-l][j];
            DP[l][j]%=Mod;
        }
        DP[l][i]=DP[l][i-1]+DP[1-l][i-1];
        DP[l][i]%=Mod;
    }
    printf ("%d\n", DP[l][N-1]);
    return 0;
}