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

vector<vector<int>> inverse_pairs(1001,vector<int>(1001,-1));

class Solution {
public:
    const int mod = 1e9 + 7 ;
    
    int kInversePairs(int n, int k) {

        if( n == 0 ) return 0;

        if( k == 0 ) return 1;

        if( inverse_pairs[n][k] != -1 ) return inverse_pairs[n][k];

        int inv_pairs = 0;

        for( int i = 0 ; i <= min( n - 1 , k ) ; i++ ) {
            (inv_pairs = inv_pairs %mod + kInversePairs( n - 1 , k - i ) %mod )%mod;
        }

        return inverse_pairs[n][k] = inv_pairs%mod;
        
    }
};


/*

    1 2 3 4 -> shift a[i] x times then it generates x pairs of inversions 

    Adding the inversion due to each number is additive

    Ex : Shift 2 : 2 1 3 4 
         Shift 4 2 times : 2 1 4 3 -> 2 4 1 3 

         number of inverse pairs = number of shifts of such nature 

         s1 + s2 + s3 + ... + sx = k for the array to be made 

Now we add 5 for an arbitrary array with y number of inversion pairs 
For an arbitrary y inverse pairs if it exists 
Adding 5 at 3 positions to the left generates 3 + y inverse pairs in total

Extending this idea further, suppose we know the number of arrangements of an array with n−1 elements, with the number of inverse pairs being 0,1,2,...,k 
Let's say being equal to count0,count1,count2,..,countk
Now, we can determine the number of arrangements of an array with nnn elements with exactly kkk inverse pairs easily.

To generate the arrangements with exactly k inverse pairs and n elements, we can add the new number nnn to all the arrangements with kkk inverse pairs at the last position. 

For the arrangements with k−1 inverse pairs , we can add n at a position 1 step from the right.

Similarly, for an element with k−i number of inverse pairs, we can add this new number nnn at a position i steps from the right. Each of these updations to the arrays leads to a new arrangement, each with the number of inverse pairs being equal to k



Developing the recursive formula for this :

if N = 0 No inverse pair exists count(0,k) = 0
if K = 0 then only 1 arrange possible for this  count(N,0) = 1

Otherwise : 
            count(n,k) = sum( count ( n - 1 , k - i ) ) 
                                where i = 0 to min( n - 1 , k - i )

About the limits :
Note that the upper limit on the summation is min(k,n−1). This is because for i>k, k−i<0. 
No arrangement exists with negative number of inverse pairs. The reason for the other factor can be seen as follows.

To generate a new arrangement adding k−i new inverse pairs after adding the nth
number, we need to add this number at the ith position from the right. For an array with size n, only n−1 maximum shifts are possible.


*/
13300