A firmware lookup table stores the keys 1, 2, ..., n (each once) in a binary search tree. The
worst-case lookup cost is the tree's height: the number of nodes on its longest path from the
root down to a leaf (an empty tree has height 0, a single node has height 1).
Return how many structurally different search trees on these n keys have height exactly
h, modulo 10**9 + 7. Two trees differ if their shapes differ (with n fixed keys the shape
decides where every key goes).
Examples
Input: n = 3, h = 2
Output: 1
Explanation: only the tree with 2 at the root and 1, 3 below it.
Input: n = 3, h = 3
Output: 4
Explanation: the other four of the five trees on three keys are chains of height 3.
Input: n = 4, h = 3
Output: 6
Constraints
0 <= n <= 100,0 <= h <= 100- Recursing on (keys, height) without remembering results takes far too long for large
n.
Goals
- Count search trees by splitting on the root key
- Count 'at most h' first and subtract to get 'exactly h'
- Tabulate the counts level by level instead of recursing blindly