#include <stdio.h>
#include <stdlib.h>

#define MOD 9999991

int v[1000001][2];

int main()
{
    FILE *fin, *fout;
    int n, i, j;
    fin = fopen("dirichlet.in", "r");
    fscanf(fin, "%d", &n);
    fclose(fin);
    v[0][0] = v[1][0] = v[0][1] = 1;
    for(i = 2; i <= n; i++){
      for(j = 1; j < i; j++){
        v[j][(i + 1) % 2] = (v[j - 1][(i + 1) % 2] + v[j][i % 2]) % MOD;
      }
      v[i][(i + 1) % 2] = v[i - 1][(i + 1) % 2];
    }
    fout = fopen("dirichlet.out", "w");
    fprintf(fout, "%d", v[n][(n + 1) % 2]);
    fclose(fout);
    return 0;
}