USACO-T031: Cow Pedigrees

/*
ID: mickyta1
TASK: nocows
LANG: C++
*/

#include <bits/stdc++.h>
using namespace std;

const int N = 200 + 5;
const int K = 100 + 5;
const int MD = 9901;

int dp[N][K];

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

    int n, depth;
    scanf("%d%d", &n, &depth);
    if(n % 2 == 0 || n < 2 * depth - 1){
        cout << "0\n";
        fclose(stdin);
        fclose(stdout);
        return 0;
    }
    dp[1][1] = 1;
    for(int d = 2; d <= depth; ++d){
        for(int i = 2 * d - 1; i <= n; i += 2){
            int sum = 0;
            for(int l = 1; l <= i / 2; l += 2){
                int r = i - l - 1;
                for(int j = 1; j < d - 1; ++j){
                    if(l != r){
                        sum = (sum + 2 * dp[l][d - 1] * dp[r][j] + 2 * dp[l][j] * dp[r][d - 1]) % MD;
                    } else {
                        sum = (sum + dp[l][d - 1] * dp[r][j] + dp[l][j] * dp[r][d - 1]) % MD;
                    }
                }
                if(l != r){
                    sum = (sum + 2 * dp[l][d - 1] * dp[r][d - 1]) % MD;
                } else {
                    sum = (sum + dp[l][d - 1] * dp[r][d - 1]) % MD;
                }
            }
            dp[i][d] = sum;
        }
    }
    cout << dp[n][depth] << '\n';

    fclose(stdin);
    fclose(stdout);
    return 0;
}