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

//Very good question
//Thought process

// 1 2 3 4 5
// can have 5 staes from here
// dp[n][k]=dp[n-1][k]+dp[n-1][k-1]+dp[n-1][k-2]+dp[n-1][k-3]+dp[n-1][k-4];

#define ll long long
#define MOD 1000000007
class Solution {
public:

    int kInversePairs(int n, int k) {
        vector<vector<ll>>dp(n+1,vector<ll>(k+1));
        if(k==0)return 1;
        for(ll i=1;i<=n;i++){
            dp[i][0]=1;
        }
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=k;j++){
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%MOD;
                if(j-i>=0)dp[i][j]=(dp[i][j]-dp[i-1][j-i]+MOD)%MOD;
            }
        }
        // for(ll i=0;i<=n;i++){
        //     for(ll j=0;j<=k;j++){
        //         cout<<dp[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        return (dp[n][k]-dp[n][k-1]+MOD)%MOD;
    }
};
38400