Count Permutations with Specified Inversions

Given a natural number n, consider all the permutations of the set {1, 2, ..., n}. For a permutation a₁, a₂, ..., a_n, a pair (a_i, a_j) is called an inversion pair if and only if i < j and a_i > a_j.

For a given permutation, let its inversion count be the total number of inversion pairs. Your task is to compute the number of permutations of {1, 2, ..., n} that have exactly k inversion pairs. Since this number can be very large, output the answer modulo $10^9+7$.

The problem can be solved using dynamic programming. One common recurrence is:

$$dp[i][j] = \sum_{x=0}^{\min(j, i-1)} dp[i-1][j-x] $$

where dp[i][j] represents the number of permutations of i numbers with exactly j inversions. Finally, you need to output dp[n][k] modulo $10^9+7$.

inputFormat

The input consists of a single line containing two integers n and k separated by space, where:

• n is the number of elements in the permutation.
• k is the exact number of inversion pairs.

outputFormat

Output a single integer, the number of permutations of {1, 2, ..., n} that have exactly k inversion pairs, taken modulo $10^9+7$.

sample

3 0

1