Confusion

Time limit1sMemory limit128 MB

Summary

Count permutations of 1..N with exactly C inversions, modulo 1e9+7, using DP with prefix sums for the given constraints.

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

Problem

Consider a sequence of length N in which each integer from 1 to N appears exactly once.

A pair of positions is called a confused pair if the earlier number in the sequence is greater than the later number. The confusion degree of a sequence is the number of confused pairs.

For example, the sequence (1, 4, 3, 2) has confusion degree 3, because its confused pairs are (4, 3), (4, 2), and (3, 2).

Given N and C, count the number of length N sequences whose confusion degree is exactly C.

Input

The first line contains two integers N and C.

1 <= N <= 1000
0 <= C <= 10000

Output

Print the number of length N sequences with confusion degree C, modulo 1,000,000,007.

Examples3

Example 1
Input
```
10 1
```
Expected output
```
9
```
Example 2
Input
```
4 3
```
Expected output
```
6
```
Example 3
Input
```
9 13
```
Expected output
```
17957
```