이진트리

이진트리 $T$ 가 있을 때, $T$의 왼쪽서브트리를 $T_l$, 오른쪽 서브트리를 $T_r$로 두면 $T$의 높이 $h(T)$는 다음과 같이 정의된다.

• $T$가 공백트리(정점의 개수가 $0$인 트리)이면 $h(T) = 0$이다.
• $T$가 공백트리가 아니면 $h(T) = \max \left\{ h(T_l) , h(T_r) \right\} + 1$ 이다.

음수가 아닌 두 정수 $N$과 $k$가 주어질 때, 정점의 개수가 $N$이고 높이가 $k$인 이진트리는 모두 몇개인지를 결정하는 프로그램을 작성하시오. 예를 들어, 정점의 개수가 $4$이고 높이가 $3$인 이진트리는 아래 보인 그림에서처럼 모두 $6$개가 있다.

입력 형식

첫째 줄에 이진트리 $T$의 정점 개수를 나타내는 정수 $N$($1\le N \le 500$)과 높이를 나타내는 정수 $k$($0 \le k \le N$)가 주어진다.

출력 형식

한 줄로 결과를 출력한다. 정점의 개수가 $N$이고 높이가 $k$인 서로 다른 이진트리 갯수를 찾아 그 값을 $1\,000\,000\,007$로 나눈 나머지를 출력한다.

예제 1

3 2

1

예제 2

4 3

6

예제 3

4 2

0

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설