class Solution:
def kInversePairs(self, n: int, k: int) -> int:
"""
I(n, k) = I(n-1, k) + I(n-1, k-1) + I(n-1, k-2) + I(n-1, k-3) + I(n-1, max(0, k - (n - 1)))
"""
dp = [0] * (k + 1)
dp[0] = 1
mod = 10 ** 9 + 7
for i in range(2, n + 1):
tmp = []
s = 0
for j in range(k + 1):
s += dp[j]
if j - i >= 0:
s -= dp[j - i]
s = s % mod
tmp.append(s)
dp = tmp
return dp[k]