Dynamic programming O(n^3)

Shariks Letter from Prostokvashino


Dear Uncle Fedor!

Do not listen to this old grumpy cat. He does not know what surprise I have prepared for him, so you can begin to write a program for him. I increased the number of brackets for him up to 300, the number of jobs per day up to 20, and complicated the task itself.

Now he must find the depth of the correctly formed bracket expression. What does it mean I read in one clever book which was lost by post officer Pechkin. The following was written there:

"Let X is a set of correctly formed bracket expressions. The length of the correctly formed expression E is the number of single brackets in E. The bracket depth D(E) of expression E is defined as follows:


For example, the length of ()(())() is 8, and the depth is 2.

Understanding that the cat is not a man, I give him such tasks, where the depth of expression is at least 1 and no more than 200 and at least 2 squares with brackets. Now let he find the number of ways to get the correct bracket sequence with given length and depth.

So hurry to send him your new program, because now I am milking a cow only until Matroskin is busy computing. Photo of thoughtful Matroskin is attached.

Your faithful friend and companion - Sharik"


Each line contains two numbers n and d, where n is the number of squares with parentheses, and d is the depth of expression. Input can contain empty lines, ignore them.


For each test case print in a separate line the number of ways to obtain the correctly formed bracket expression of length n and depth d.

Time limit 4 seconds
Memory limit 256 MiB
Input example #1
6 2
300 150
Output example #1
Author Анатолий Присяжнюк