20054번 - 트리 가짓수 세기

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

다음은 BST의 삽입하는 함수를 수도-코드(pseudo code)로 작성한 것이다.

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$로 나눈 나머지를 출력한다.