Expressions

Time limit1sMemory limit128 MB

Summary

Count balanced parenthesis strings of a given total length that have exactly a given maximum nesting depth.

Level: Medium6 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

Let $X$ be the smallest set defined by the following rules:

the empty string belongs to $X$ ;
if $A$ and $B$ belong to $X$ , then both $(A)$ and $AB$ belong to $X$ .

The elements of $X$ are called correctly built parenthesis expressions. For example, these strings are correctly built parenthesis expressions:

()(())()
(()(()))

while these are not:

(()))(()
())(()

Let $E$ be a correctly built parenthesis expression. The length of $E$ is the number of single parentheses in $E$ . The depth $D(E)$ of $E$ is defined by:

D(E) = \begin{cases} 0 & \text{if } E \text{ is empty} \\ D(A) + 1 & \text{if } E = (A) \text{ with } A \in X \\ \max(D(A), D(B)) & \text{if } E = AB \text{ with } A, B \in X \end{cases}

Given two positive integers $n$ and $d$ , determine how many correctly built parenthesis expressions have length exactly $n$ and depth exactly $d$ .

Input

A single line containing two integers $n$ and $d$ separated by one space, with $2 \le n \le 38$ and $1 \le d \le 19$ .

Output

Print a single integer: the number of correctly built parenthesis expressions of length $n$ and depth $d$ .

Hint

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

(())()
()(())
(()())

Examples4

Example 1
Input
```
6 2
```
Expected output
```
3
```
Example 2
Input
```
2 1
```
Expected output
```
1
```
Example 3
Input
```
4 2
```
Expected output
```
1
```
Example 4
Input
```
6 1
```
Expected output
```
1
```