트리 가짓수 세기

이진 검색 트리(BST, Binary Search Tree)는 모든 노드가 최대 $2$개의 자식 노드를 가지는 트리이다. 어떤 노드에 쓰여 있는 수가 $X$라면, 그 노드의 왼쪽 서브트리에는 $X$보다 작은 수만, 오른쪽 서브트리에는 $X$보다 큰 수만 저장되어 있어야 한다.

다음은 BST에 수를 삽입하는 함수를 수도 코드로 작성한 것이다.

insert(number X, node N)
    if X가 노드 N에 있는 수보다 작다면
        if N의 왼쪽 자식이 없다면
            X를 포함하는 새 노드를 만든 뒤, N의 왼쪽 자식으로 만든다
        else
            insert(X, N의 왼쪽 자식)
    else (X가 노드 N에 있는 수보다 크다면)
        if N의 오른쪽 자식이 없다면
            X를 포함하는 새 노드를 만든 뒤, N의 오른쪽 자식으로 만든다
        else
            insert(X, N의 오른쪽 자식)

첫 번째로 삽입하는 수를 루트로 놓고, 그 뒤에 삽입하는 모든 수 X에 대해 insert(X, root)를 호출한다.

트리의 높이는 루트 노드에서 리프 노드까지의 경로 중 가장 긴 경로 위에 있는 노드의 개수이다. 리프 노드는 자식 노드가 없는 노드를 뜻한다.

$1$부터 $N$까지의 수를 BST에 삽입하려고 한다. 삽입 순서를 자유롭게 정할 수 있을 때, 높이가 $K$ 이하인 BST의 가짓수를 구해보자. BST의 루트 노드는 높이가 1이라고 가정한다.

$2$ $1$ $3$ 순으로 넣었을 때 만들어지는 BST와 $2$ $3$ $1$ 순으로 넣었을 때 만들어지는 BST는 같은 경우이고, $3$ $2$ $1$ $4$와 $2$ $1$ $3$ $4$ 순으로 넣었을 때 만들어지는 BST는 서로 다른 경우이다.

구하려는 경우의 수는 매우 커질 수 있으므로 답을 $10^9+7$로 나눈 나머지를 출력한다.

첫 번째 줄에 두 정수 $N$, $K$가 공백으로 구분되어 주어진다. ($1 \leq N \leq 3500,\, 1 \leq K \leq 12$)

만들어지는 BST의 경우의 수를 $10^9+7$로 나눈 나머지를 출력한다.