#include <cstdio>

#define Mod 9999991
#define NMax 1005

using namespace std;

long long N, S, DP[NMax][NMax];

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