For an integer array nums, an inverse pair is a pair of integers [i, j] where 0 &lt;= i &lt; j &lt; nums.length and nums[i] &gt; nums[j].

Given two integers n and k, return the number of different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo 109 + 7.

&nbsp;
Example 1:

Input: n = 3, k = 0
Output: 1
Explanation: Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pairs.


Example 2:

Input: n = 3, k = 1
Output: 2
Explanation: The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.


&nbsp;
Constraints:


	1 &lt;= n &lt;= 1000
	0 &lt;= k &lt;= 1000


class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        # Complexity:
        # - Time: O(N*K)
        # - Space: O(K)

        # Special cases that can be short-circuited right away
        # - For k=0, there's only one solution, which is having the numbers in sorted order
        #     DP(n, 0) = 1
        if k == 0:
            return 1
        # - There can't be more than n*(n-1)/2 inverse pairs, which corresponds to the numbers in reverse order
        #     DP(n, k) = 0 for all k > n*(n-1)/2
        if k > n * (n - 1) // 2:
            return 0

        # For the general case, we notice that:
        #     DP(n+1, k) = sum(DP(n, i) for i in [max(0, k-n), k])
        # i.e., adding an additional number (the biggest one n+1):
        # - We can have it at the end, in which case it doesn't create any reverse pairs,
        #   and so the number of configurations with k reverse pairs is DP(n,k)
        # - Or we can have it one before the end, in which case it creates exactly reverse pairs,
        #   and so the number of configurations with k reverse pairs is DP(n,k-1)
        # - And so on and so forth, such that having it `i` places before the end create exactly `i` reverse pairs,
        #   and so the number of configurations with k reverse pairs is DP(n,k-i)
        # This relationship allows us to compute things iteratively with a rolling window sum
        kLine = [0] * (k + 1)
        kLine[0] = 1
        previousKLine = kLine.copy()
        maxFeasibleK = 0
        for m in range(2, n + 1):
            previousKLine, kLine = kLine, previousKLine
            rollingWindowSum = 1
            maxFeasibleK += m - 1
            endKLineIdx = min(k, maxFeasibleK) + 1
            intermediateKLineIdx = min(endKLineIdx, m)
            for kLineIdx in range(1, intermediateKLineIdx):
                rollingWindowSum = (rollingWindowSum + previousKLine[kLineIdx]) % _MODULO
                kLine[kLineIdx] = rollingWindowSum
            for kLineIdx in range(intermediateKLineIdx, endKLineIdx):
                rollingWindowSum = (rollingWindowSum + previousKLine[kLineIdx] - previousKLine[kLineIdx - m]) % _MODULO
                kLine[kLineIdx] = rollingWindowSum
        return kLine[k]


_MODULO = 10 ** 9 + 7
class Solution {
    public int kInversePairs(int n, int k) {
        int MOD = 1000000007;
        int[][] opt = new int[k + 1][n];
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    opt[i][j] = 1;
                } else if (j > 0) {
                    opt[i][j] = (opt[i - 1][j] + opt[i][j - 1]) % MOD;
                    if (i >= j + 1) {
                        opt[i][j] = (opt[i][j] - opt[i - j - 1][j - 1] + MOD) % MOD;
                    }
                }
            }
        }

        return opt[k][n - 1];
    }
}
class Solution {
public:
    int mod = (int)(1e9 + 7);
    int dp[1001][1001] = {};
    
    int kInversePairs(int n, int k) {
        //base case
        if(k<=0) return k==0;
        
        if(dp[n][k]==0){
            dp[n][k] = 1;
            
            for(int i=0; i<n; i++){
                dp[n][k] = (dp[n][k] + kInversePairs(n-1,k-i))%mod;
            }
        }
        return dp[n][k]-1;
    }
};
var kInversePairs = function(n, k) {
    const dp = new Array(n+1).fill(0).map(el => new Array(k+1).fill(0))
    const MOD = Math.pow(10, 9) + 7

    for(let i = 0; i < n+1; i++) {
        dp[i][0] = 1
    }

    for(let i = 1; i <= n; i++) {
        for(let j = 1; j <= k; j++) {
            dp[i][j] = (dp[i][j-1] + dp[i-1][j] % MOD) - (j >= i ? dp[i-1][j-i] : 0)%MOD
        }
    }

    return dp[n][k] % MOD
};
K Inverse Pairs Array