"EXPRESSIONS" (POLAND)

Let X be the set of correctly built parenthesis expressions. The elements of X are strings consisting only of the characters ( and ). The set X is defined as follows:

• an empty string belongs to X
• if A belongs to X, then (A) belongs to X
• if both A and B belong to X, then the concatenation AB belongs to X.
For example, the following strings are correctly built parenthesis expressions (and therefore belong to the set X):

()(())()

(()(()))

The expressions below are not correctly built parenthesis expressions (and are thus not in X):

(()))(()

())(()

Let E be a correctly built parenthesis expression (therefore E is a string belonging to X).

The length of E is the number of single parenthesis (characters) in E.

The depth D(E) of E is defined as follows:

ì 0 if E is empty
D(E)= í D(A)+1 if E = (A), and A is in X
î max(D(A),D(B)) if E = AB, and A, B are in X

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

What is the number of correctly built parenthesis expressions of length n and depth d, for given positive integers n and d?

Write a program which

• reads two integers n and d from the text file PAR.IN;
• computes the number of correctly built parenthesis expressions of length n and depth d;
• writes the result into the text file PAR.OUT
Input data
The only line of the input file PAR.IN contains two integers n and d separated by a single space character, 2 £ n £ 38, 1 £ d £ 19.

Output data
The only line of the output file PAR.OUT should contain a single integer - the number of correctly built parenthesis expressions of length n and depth d.

Example
Input data (file PAR.IN)             Output data (file PAR.OUT)
6 2                 3

There are exactly three correctly built parenthesis expressions of length 6 and depth 2:
(())()
()(())
(()())