Let's try for a top-down dp. Suppose we know `dp[n][k]`

, the number of permutations of (1...n) with k inverse pairs.

Looking at a potential recursion for `dp[n+1][k]`

, depending on where we put the element (n+1) in our permutation, we may add 0, 1, 2, ..., n new inverse pairs. For example, if we have some permutation of 1...4, then:

- 5 x x x x creates 4 new inverse pairs
- x 5 x x x creates 3 new inverse pairs
- ...
- x x x x 5 creates 0 new inverse pairs

where in the above I'm representing any permutation of 1...4 with x's.

Thus, `dp[n+1][k] = sum_{x=0..n} dp[n][k-x]`

.

This dp has `NK`

states with `K/2`

work, which isn't fast enough. We need to optimize further.

Let `ds[n][k] = sum_{x=0..k-1} dp[n][x]`

.

Then `dp[n+1][k] = ds[n][k+1] - ds[n][k-n]`

,

and the left hand side is `ds[n+1][k+1] - ds[n+1][k]`

.

Thus, we can perform all calculations in terms of `ds`

.

Finally, to save space, we will only store the two most recent rows of `ds`

, using `ds`

and `new`

.

In the code, we refer to `-ds[n][k-n+1]`

instead of `-ds[n][k-n]`

because the `n`

being considered is actually n+1. For example, when `n=2`

, we are appending information about `ds[2][k]`

to `new`

, so our formula of `dp[n+1][k] = ds[n][k+1] - ds[n][k-n]`

is `dp[2][k] = ds[1][k+1] - ds[1][k-1]`

.

```
def kInversePairs(self, N, K):
MOD = 10**9 + 7
ds = [0] + [1] * (K + 1)
for n in xrange(2, N+1):
new = [0]
for k in xrange(K+1):
v = ds[k+1]
v -= ds[k-n+1] if k >= n else 0
new.append( (new[-1] + v) % MOD )
ds = new
return (ds[K+1] - ds[K]) % MOD
```