Farmer John is considering purchasing a new herd of cows. In this new herd, each mother cow gives birth to two children. The relationships among the cows can easily be represented by one or more binary trees with a total of N (3 <= N < 200) nodes. The trees have these properties:

• The degree of each node is 0 or 2. The degree is the count of the node's immediate children.
• The height of the tree is equal to K (1 < K <100). The height is the number of nodes on the longest path from the root to any leaf; a leaf is a node with no children.

How many different possible pedigree structures are there? A pedigree is different if its tree structure differs from that of another pedigree. Output the remainder when the total number of different possible pedigrees is divided by 9901.

PROGRAM NAME: nocows

INPUT FORMAT

• Line 1: Two space-separated integers, N and K.

SAMPLE INPUT (file nocows.in)

5 3

OUTPUT FORMAT

• Line 1: One single integer number representing the number of possible pedigrees MODULO 9901.

SAMPLE OUTPUT (file nocows.out)

2

OUTPUT DETAILS

           @                   @
/ \                 / \
@   @      and      @   @
/ \                     / \
@   @                   @   @

題意：
給出一顆二叉樹的節點數n和高度m。計算滿足n和m的二叉樹數個數。
ans = (n, m) - (n, m - 1);
節點數為n高度小于等于m的數個數減去節點數為n高度小于等于m-1的數個數。
因為(n, m)里含有高度小于m的數個數，那些是不符合題意要求的,題意要求的數高度一定得是m。

代碼入下：

/*
LANG: C
TASK: nocows
*/
#include<stdio.h>
int v[210][110];
void Set(int n, int m)
{
    int i, j;
    for (i = 0; i <= n; i++)
    {
        for (j = 0; j <= m; j++)
        {
            v[i][j] = -1;
        }
    }
}
int Deal(int num, int dep)//求出高度小于或等于dep的情況數,//這個對(7，4)-(7，3)就清楚了。(7, 4)里有一個事高度為3的情況 
{
    int i, sum = 0;
    if (dep == 0)//如果高度是0，不存在情況。所以情況數為0 
    {
        return 0;
    }
    if (num == 1)//如果只有一個節點。不管高度多少，允許的情況就是一個節點的高度只為1.情況數為1 
    {
        return 1;
    }
    if (v[num][dep] != -1)//表示該情況沒被計算過。 
    {
        return v[num][dep];
    }
    //計算左右子數組合的情況數，節點數為偶數時，情況數是0。只需要計算奇數情況 
    for (i = 1; i < num - 1; i += 2) 
    {
        //由于左右字數節點數不同，所以Deal(i, dep - 1)和Deal(num - 1 - i, dep - 1)不存在相同的結構 
        //所以要計算 Deal(i, dep - 1)*Deal(num - 1 - i, dep - 1) 和 Deal(num - 1 - i, dep - 1)*Deal(i, dep - 1)
        //當i = num - 1 - i ，只計算了一次。 
        sum = (sum + Deal(i, dep - 1) * Deal(num - 1 - i, dep - 1)) % 9901;
    }
    v[num][dep] = sum;//保存節點數為num，高度小于等于dep的情況數
    return sum;
}
int main()
{
    freopen("nocows.in", "r", stdin);
    freopen("nocows.out", "w", stdout);
    int t, n, m;
    scanf("%d%d", &n, &m);
    Set(n, m);
    t = (9901 + Deal(n, m) - Deal(n, m - 1)) % 9901;//求高度恰好為m的情況數 
    printf("%d\n", t);
    fclose(stdin);
    fclose(stdout);
    //system("pause");
    return 0;
}