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

<p>Given two integers n and k, return the number of different arrays consisting of numbers from <code>1</code> to <code>n</code> such that there are exactly <code>k</code> <strong>inverse pairs</strong>. Since the answer can be huge, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
	<li><code>0 &lt;= k &lt;= 1000</code></li>
</ul>

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        # for k=0, dp=1, just 1..n    O(nk) time in loops, O(k) space
        dp, mod = [1]+[0] * k, 1_000_000_007
        # dp[j] is the number of permutations with j inverse pairs, for i numbers
        for i in range(n):  # add a new number
            tmp, sm = [], 0
            for j in range(k + 1):
                sm += dp[j]  # cumulative sum
                if j >= i+1: sm -= dp[j-i-1]  # minus invalid pairs
                sm %= mod
                tmp.append(sm)
            dp = tmp
        return dp[k]
        # Almost all permutations of 1,...,n with k−1 pairs can be transformed to have k pairs by swapping the n to move it to the front of the array - since n is greater than all elements, it increases the number of inverse pairs by one. Hence the first term.
        # However, this doesn't lead to any permutations which have n at the end of the array. But to count these, we simply need the number of permutations of 1,...,n−1 with k pairs, which is a subproblem. Hence the second term.
        # We also 'overcount' for the initial permutations that start with n at the front of the array (since you can't move it further forward). Since n is greater than all other elements, in these cases it contributes to n−1 of the pairs. Thus it's equivalent to solve how to arrange the remaining n−1 numbers with (k−1)−(n−1)=k−n pairs, which is also a subproblem. Hence the third term.
        #

        # works but time out  O(n^2 * k)
        # MOD = 1_000_000_007
        # @cache
        # def count(n, k):
        #     if n == 0: return k== 0
        #     if k < 0: return 0
        #     res = 0
        #     for i in range(n):  # i is the number of inverse pairs we create when using i
        #         res = (res + count(n-1, k-i)) % MOD
        #     return res
        # return count(n, k)

        # dp[i][j] = number of arrays with j inverse pairs for given i elements

        # https://leetcode.com/problems/k-inverse-pairs-array/?envType=company&envId=facebook&favoriteSlug=facebook-three-months
        # https://leetcode.com/problems/k-inverse-pairs-array/solutions/4632287/simple-3-line-o-nk-python3-solution-with-intuitive-explanation/?envType=company&envId=facebook&favoriteSlug=facebook-three-months
        # works but timeout
        # @cache
        # def dp(n, k):
        #     if k == 0: return 1
        #     if n == 1 or k < 0: return 0
        #     # dp(n, k-1): any k-1 pair, move n to left, is a k pair
        #     # dp(n-1, k): not use n
        #     # dp(n-1, k-n): 
        #     return dp(n, k-1) + dp(n-1, k) - dp(n-1, k-n)
        # return dp(n, k) % (10**9+7)
16900