cho.sh
Notes
Loading...

Counting Full Binary Trees

Time limit

2s

Memory limit

128 MB

Problem

Count how many different binary trees satisfy all of the following conditions.

  1. The tree has exactly n nodes. (1 <= n < 200)
  2. Every node has degree 0 or 2. The degree of a node is the number of children it has.
  3. The height of the tree is exactly k. (1 < k < 100) The height is the number of nodes on the longest path from the root to a leaf. A leaf is a node with no children.

Because the tree is binary, changing the placement of left and right children can make a different tree.

The answer can be very large, so compute it modulo 9901.

Input

The first line contains two integers n and k.

Output

Output the number of different binary trees satisfying the conditions, modulo 9901.