Vera and Sorting

Time limit2sMemory limit256 MB

Summary

Count permutations of size N for which a recursive quicksort-like routine performs exactly K comparison steps, modulo 1e9+7.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Recursion, Math
Solved: No attempts yet

Problem

Vera invented a new sorting algorithm. She wrote the Python function below to count how many steps her algorithm takes.

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)

A permutation $P$ of size $N$ is an ordered sequence of integers $P_1, P_2, \dots, P_N$ whose $N$ entries are distinct positive integers, each of them at most $N$ .

You are given integers $N$ and $K$ . Count the permutations $P$ of size $N$ for which $steps(P)$ returns $K$ . The count can be large, so print it modulo $10^9 + 7$ .

Input

The first line contains two integers $N$ and $K$ separated by a space.

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

Output

Print the number of such permutations modulo $10^9 + 7$ on a single line.

Note

For $N = 3$ and $K = 5$ the two valid permutations are $(2, 1, 3)$ and $(2, 3, 1)$ .

Examples3

Example 1
Input
```
3 5
```
Expected output
```
2
```
Example 2
Input
```
5 29
```
Expected output
```
0
```
Example 3
Input
```
20 100
```
Expected output
```
262859528
```