#include <cstdio>
#include <iostream>

using namespace std;

int v[ 50 ], N, sol;

void gen(int k, int sum){
    int i;
    if( k > N ){
        if( sum == N ){
            sol ++;
            sol %= 9999991;
        }
    }
    else
        for( i = 0 ; i + sum <= k ; ++i )
        {
            v[ k ] = i;
            gen( k + 1, i + sum );
        }
}

int main()
{
    freopen("dirichlet.in","r",stdin);
    freopen("dirichlet.out","w",stdout);
    cin >> N;
    gen(1,0);
    cout << sol << "\n";
    return 0;
}