Count permutations with exactly n inversions

You are given two integers m and n.

Consider all permutations of the array [1, 2, ..., m] (each number from 1 to m appears exactly once). A permutation perm (0-indexed) has an inversion pair (x, y) if:

• 0 <= x < y < m, and
• perm[x] > perm[y]

A permutation is called special if it contains exactly n inversions.

Return the number of special permutations modulo 10^9 + 7.

Examples

1. Input: m = 3, n = 0
   Output: 1
   

   Explanation: Only [1, 2, 3] has 0 inversions.

2. Input: m = 3, n = 1
   Output: 2
   

   Explanation: [1, 3, 2] and [2, 1, 3] each have exactly 1 inversion.

Constraints

• 1 <= m <= 1000
• 0 <= n <= 1000

Count permutations with exactly n inversions

You are given two integers m and n.

Consider all permutations of the array [1, 2, ..., m] (each number from 1 to m appears exactly once). A permutation perm (0-indexed) has an inversion pair (x, y) if:

• 0 <= x < y < m, and
• perm[x] > perm[y]

A permutation is called special if it contains exactly n inversions.

Return the number of special permutations modulo 10^9 + 7.

Examples

1. Input: m = 3, n = 0 -> Output: 1 (only [1, 2, 3] has 0 inversions).
2. Input: m = 3, n = 1 -> Output: 2 ([1, 3, 2] and [2, 1, 3]).

Constraints

• 1 <= m <= 1000
• 0 <= n <= 1000

Approach

Let dp[i][j] be the number of permutations of i elements with exactly j inversions. Inserting the i-th element into a permutation of i-1 elements can create between 0 and i-1 new inversions, so dp[i][j] = sum_{k=0}^{min(j, i-1)} dp[i-1][j-k]. The inner sum is a sliding window, so maintain a prefix-sum array to evaluate each state in O(1), giving an overall O(m*n) time / O(n) space algorithm.

Hints

1. Define dp[i][j] = number of permutations of i elements with exactly j inversions. The answer is dp[m][n].
2. Inserting the largest element into a permutation of i-1 elements at the position that leaves k elements to its right adds exactly k new inversions, with 0 <= k <= i-1. So dp[i][j] = sum_{k=0}^{min(j, i-1)} dp[i-1][j-k].
3. The inner summation is a sliding window of width i over the previous row. Use a prefix-sum array to compute each new[j] in O(1), reducing the total work to O(m*n). Take care with the modulo on subtraction (add MOD or rely on Python's non-negative modulo).