K Inverse Pairs Array

Consider all permutations of the integers 1 through n, using each integer exactly once. An inverse pair consists of indices i < j whose values satisfy nums[i] > nums[j]. Return how many permutations have exactly k inverse pairs, modulo 1000000007.

Example 1:

Input: n = 3
k = 2

Output: 2

Explanation: The permutations [2,3,1] and [3,1,2] each contain exactly two inverse pairs. No other permutation of 1, 2, and 3 has exactly two.

Example 2:

Input: n = 3
k = 3

Output: 1

Explanation: Only [3,2,1] has three inverse pairs: the value pairs (3,2), (3,1), and (2,1).

Example 3:

Input: n = 2
k = 2

Output: 0

Explanation: A permutation of two elements has only one pair of indices, so it cannot contain two inverse pairs.

Constraints:

• 1 <= n <= 1000
• 0 <= k <= 1000