<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:
        # dp[j] is the inverse paris cnt for j inverses
        # so ans will be dp[k]
        dp = [0] * (k + 1)

        # initialize the row for n = 1
        # For 1 element, only dp[0] = 1, else should be 0
        dp[0] = 1

        for row in range(2, n + 1):
            nxt_dp = [0] * (k + 1)
            for pair in range(k + 1):
                if pair == 0:
                    nxt_dp[0] = 1
                    continue
                # adding row to previous sequence will add added_pair
                # the range is 0 if placed at the end, and row - 1 if placed at top
                # for nxt_dp[pair], it is the sum for dp[min(0, pair-row + 1)] to dp[pair]
                # it is like a sliding window of size pair - row, we can add one from right and subtract one from left
                nxt_dp[pair] = nxt_dp[pair - 1] + dp[pair]
                if pair - row >= 0:
                    nxt_dp[pair] -= dp[pair - row]
                nxt_dp[pair] %= 10**9 + 7
            dp = nxt_dp

        return dp[k]


"""
[1,2,3] k = 1 -> 2
{(1, 1) : 0, (2, 2):0 (1, 0): 1, (3, 1): 1, {2, 0}: 1}
n = 3, k = 1
kInversePairs(3, 1)
    pairs = 2
    i 1 (0-1)
    n = 2, k = 0
   



7:01

[1, 2, 3, 4] k = 1
[2, 1, 3, 4], [1, 3, 2, 4]....
ans = n - 1

solution:
1. (n, k)  = (n-1, k) + (n-1, k - 1) + (n-1, k-2) + .... (n - 1, 1) + (n - 1, 0)

max pairs = C(2, n) = n(n-1)/2

time O(n*k^2), space O(n*k)

"""
16800