#include <cstdio>
#define MOD 9999991

int N;

int mat[2][2001];
int L, C;

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

    L = 0;
    C = 1;

    scanf("%d", &N);

    mat[L][0] = 1;
    mat[C][0] = 1;

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

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