베라와 정렬

베라는 새로운 정렬 알고리즘을 만들었다. 그 알고리즘이 몇 단계를 거치는지 세려고 베라가 작성한 파이썬 함수는 다음과 같다.

def steps(array):
    if len(array) == 0:
        return 0
    pivot = array[0]
    count = 0
    lesser = []
    greater = []
    for element in array:
        count += 1
        if element < pivot:
            lesser.append(element)
        elif element > pivot:
            greater.append(element)
    return count + steps(lesser) + steps(greater)

크기가 $N$인 순열 $P$는 정수열 $P_1, P_2, \dots, P_N$이며, 원소는 모두 다르고 각각 $N$ 이하의 양의 정수다.

정수 $N$과 $K$가 주어진다. $steps(P)$가 $K$를 반환하는 크기 $N$의 순열 $P$가 몇 개인지 세어라. 답이 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫째 줄에 정수 $N$과 $K$가 공백으로 구분되어 주어진다.

• $1 \le N \le 30$
• $1 \le K \le 900$

조건을 만족하는 순열의 개수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.

$N = 3$, $K = 5$일 때 조건을 만족하는 순열은 $(2, 1, 3)$과 $(2, 3, 1)$ 두 개다.