<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>

# https://leetcode.com/problems/k-inverse-pairs-array/solutions/4634349/recursive-solution-with-explanation-python-3
# Explanation of the problem
# Imagine you have some numbers from 1 to n, and you want to arrange them in different ways. You also want to count how many times a bigger number comes before a smaller number in each arrangement. For example, if n is 3, you have these possible arrangements:

# 1, 2, 3 -> no bigger number comes before a smaller number, so the count is 0
# 1, 3, 2 -> only 3 comes before 2, so the count is 1
# 2, 1, 3 -> only 2 comes before 1, so the count is 1
# 2, 3, 1 -> 2 comes before 1, and 3 comes before 1, so the count is 2
# 3, 1, 2 -> 3 comes before 1, and 3 comes before 2, so the count is 2
# 3, 2, 1 -> 3 comes before 2, 3 comes before 1, and 2 comes before 1, so the count is 3
# Now, suppose you want to know how many arrangements have exactly k times that a bigger number comes before a smaller number. For example, if k is 2, then there are only two arrangements that have exactly 2 times that a bigger number comes before a smaller number: 2, 3, 1 and 3, 1, 2.

# Approach
# Use dynamic programming
# Base cases:

# If k is 0, then there is only one way to arrange the numbers in increasing order, like 1, 2, 3. So the function returns 1.
# If k is negative, then there is no way to arrange the numbers that has a negative number of times that a bigger number comes before a smaller number. Return 0.
# If n is 1, then there is only one element in an array - it is not possible to creae a pair from 1 element. Return 0.
# Recursive section of desidion tree
# I don't know how can you find out it but yourself
# It is based on a formula of "recurrence relation for the binomial coefficient"
# The logic behind the formula dp(n, k) = dp(n - 1, k) + dp(n, k - 1) - dp(n - 1, k - n) is based on the idea of adding and removing elements from the set of size n.
# This means:

# How many ways to arrange n numbers with k pairs of numbers that are out of order?
# It is equal to the sum of:

# How many ways to arrange n - 1 numbers with k pairs of numbers that are out of order, and then add n to the end. This does not change the number of pairs of numbers that are out of order, because n is bigger than all the other numbers and it is at the end.
# How many ways to arrange n numbers with k - 1 pairs of numbers that are out of order, and then remove n from the end. This reduces the number of pairs of numbers that are out of order by 1, because n is bigger than all the other numbers and it removes one pair of numbers that are out of order with the last number in the original arrangement.
# How many ways to arrange n - 1 numbers with k - n pairs of numbers that are out of order, and then add 1 to the end. This increases the number of pairs of numbers that are out of order by n - 1, because 1 is smaller than all the other numbers and it creates n - 1 pairs of numbers that are out of order with the last number in the original arrangement.
# Complexity
# Time complexity:
# O(N∗K)

# Space complexity:
# O(N∗K)

# class Solution:
#     def kInversePairs(self, n: int, k: int) -> int:
#         MOD = 10**9 + 7
#         @cache
#         def dp(n, k):
#             if k == 0:
#                 # there is exactly one way to arrange the array (in increasing order)
#                 return 1
#             if k < 0:
#                 # k in negative area - ivalid
#                 return 0
#             if n == 1:
#                 # can't create any (k) pairs if array has only 1 element
#                 return 0
            
#             return (dp(n - 1, k) + dp(n, k - 1) - dp(n - 1, k - n)) % MOD
#         return dp(n, k)

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        MOD = 1000000007
        dp = [0] * (k + 1)
        dp[0] = 1
        for i in range(2, n + 1):
            for j in range(1, k + 1):
                dp[j] = (dp[j] + dp[j - 1]) % MOD
            for j in range(k, i - 1, -1):
                dp[j] = (dp[j] - dp[j - i] + MOD) % MOD
        return dp[k]
16700