#include <cstdio>
#define MOD 9999991

int N;

int mat[2001][2001];

int main()
{
    freopen("dirichlet.in", "r", stdin);
    freopen("dirichlet.out", "w", stdout);

    scanf("%d", &N);

    for(int i = 0; i <= N; i++)
    {
        mat[i][0] = 1;
        mat[i][1] = i;
    }

    for(int i = 1; i <=N; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            mat[i][j] = (mat[i-1][j] + mat[i][j-1])%MOD;
        }
    }

    printf("%d", mat[N][N]);
    return 0;
}