Counting Unlabeled Full Binary Trees

Given two integers n and k, count the number of different structures of unlabeled full binary trees with exactly n nodes and exactly depth k. A full binary tree is defined as a tree in which every node has either 0 or 2 children. The depth of the tree is defined as the length of the longest path from the root (at depth 1) to any leaf. Since the number can be large, output the answer modulo 9901.

The answer should be computed using the following definitions in LaTeX:

Let \(DP(n,k)\) denote the number of full binary trees with n nodes and exact depth \(k\). Then for \(n = 1\) (a single node tree), we have \[ DP(1,1)=1, \quad DP(1,k)=0\text{ for } k>1. \] For \(n \ge 3\) (note that n must be odd), the recurrence is given by \[ DP(n,k)=\sum_{i=1,\, i\ odd}^{n-2} \Bigl( DP(i,k-1)\cdot G(n-1-i,k-1) + G(i,k-1)\cdot DP(n-1-i,k-1) - DP(i,k-1)\cdot DP(n-1-i,k-1) \Bigr), \] where \(G(n,k)=\sum_{j=1}^{k} DP(n,j)\) counts trees with n nodes and height at most \(k\).

Your task is to compute \(DP(n,k) \bmod 9901\).

inputFormat

The input consists of a single line with two space separated integers: n and k.

It is guaranteed that n is an odd positive integer.

outputFormat

Output a single integer which is the number of unlabeled full binary trees with exactly n nodes and exactly depth k, computed modulo 9901.

sample

1 1

1