Inversions

Interview

Time limit1sMemory limit128 MB

Summary

Count permutations of size n that have exactly k inversions, modulo 30011, using the Mahonian number recurrence with a sliding window over prefix sums.

Level: Medium6 of 10
Topics: Dynamic programming, Combinatorics, Prefix sum, Sliding window
Solved: No attempts yet

Problem

A sequence $x_1, x_2, \dots, x_n$ of distinct integers is a permutation of size $n$ when $1 \le x_i \le n$ holds for every $1 \le i \le n$ . For a permutation, an inversion is a pair of indices $1 \le i < j \le n$ with $x_i > x_j$ .

Given $n$ and $k$ , count how many permutations of size $n$ have exactly $k$ inversions.

Input

A single line with two integers $n$ and $k$ ( $1 \le n \le 500$ , $0 \le k \le n(n-1)/2$ ), separated by one space: the size of the permutation and the target number of inversions.

Output

Print one line with the number of permutations of size $n$ that have exactly $k$ inversions, taken modulo $30011$ .

Hint

The permutations of size $3$ with $2$ inversions are $(2, 3, 1)$ and $(3, 1, 2)$ , so the answer for $n = 3$ , $k = 2$ is $2$ .

Examples2

Example 1
Input
```
3 2
```
Expected output
```
2
```
Example 2
Input
```
4 3
```
Expected output
```
6
```