Utkarsh and Binary Trees

3.9

841 votes
Combinatorics, Mathematics, Dynamic Programming, Approved, Medium
Problem

On his Birthday, Utkarsh was given a gift he was most fond of. Utkarsh was given a box which contained lot of Binary Search Trees. When he started to examine the BST's, to his amazement he found that the box contained all possible BST's that can be made using the first N natural numbers.

But he did not like very tall trees. Therefore he threw all the BST's that had height greater than H out of the box.
Now the next exciting thing he wanted to do was to count the sum of the integers that are present on the root of each of the remaining tree in the box.

Output the answer Modulo 1000000007

Costraints
0 < N,H<=500

INPUT
One line containing N and H.
OUTPUT
The answer to the problem.

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

There are 2 trees with 1 as root, 1 tree with 2 as root, 2 trees with 3 as root.
Therefore 2 * 1 + 1 * 2 + 2 * 3 = 10

Editor Image

?