utkarsh-and-binary-trees

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.

SAMPLE INPUT
3 3

SAMPLE OUTPUT
10

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

Source: hackerearth | Difficulty: MEDIUM
Tags: Dynamic programming

Combinatorics

Mathematics


Solutions: