시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6 1 1 16.667%

문제

Let X be the smallest set defined as follows

  • an empty string belongs to X,
  • if A, B belong to X then both, (A) and AB, belong to X.

The elements of X are called correctly built parenthesis expressions. The following strings are correctly built parenthesis expressions:

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

The expressions below are not correctly built parenthesis expressions:

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

Let E be a correctly built parenthesis expression. The length of E is the number of single parenthesis 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 

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 input;
  • computes the number of correctly built parenthesis expressions of length n and depth d;
  • writes the result into the output.

입력

The only line of the input contains two integers n and d separated by a single space character, 2 ≤ n ≤ 38, 1 ≤ d ≤ 19.

출력

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

예제 입력 1

6 2

예제 출력 1

3

힌트

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

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