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

#pragma GCC optimize("unroll-loops,O3,Ofast") //even 10^8+ also works with this
#pragma GCC target("avx2,avx,fma,bmi,bmi2,lzcnt,popcnt")
// typedef long long ll;

#define ll int
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
#define rt return;
#define set_bits(a) __builtin_popcountll(a)
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define disp(a) {for(int i=0;i<a.size();i++) cout<<a[i]<<" "; cout<<endl;}
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define inp(a) {for(int i=0;i<(a).size();i++) cin>>(a)[i];}
#define fill(a,b) memset(a, b, sizeof(a))
#define prt(a) cout<<(a)<<endl;
#define endl "\n"
#define NO cout<<"NO"<<endl;
#define YES cout<<"YES"<<endl;
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define double double
#define de(a) cout<<"("<<a<<")"<<endl;
#define de2(a) cout<<"*"<<a<<"*"<<endl;
#define ft front()
#define bk back()
#define nl cout<<endl;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define cont continue;
#define vpll vector<pair<ll,ll>>
#define vvii vector<vi>
#define vi vector<int>
#define vvpll vector<vector<pair<ll,ll>>>
#define pll pair<ll,ll>
#define ld long double

template<class T> using minpq = priority_queue<T,vector<T>,greater<T>>;
template<class T> using maxpq = priority_queue<T>;

//const ll M=998244353;
const ll M=1e9+7;
const ll N=14;  
const ll inf=1e9; //keeping inf may not give soln every time,try 1e9, 1e15

bool isOverflow(ll x, ll y){return (x > LLONG_MAX / y or y > LLONG_MAX / x);}
ll bit(ll n,ll i){return (n&(1LL<<i)) ? 1 : 0;}
void unset(ll &n,ll i){ if((n&(1LL<<i))!=0) n-=(1LL<<i);}
void makeset(ll &n,ll i){ if((n&(1LL<<i))==0) n+=(1LL<<i);}
ll add(ll a,ll b){return ((a%M) + (b%M))%M;}
ll mul(ll a,ll b){return ((a%M) * (b%M))%M;}
ll sub(ll a,ll b){return ((a%M) - (b%M) + M)%M;}
ll isPail(string &s){string t=s; reverse(all(t)); return s==t; }

vll dx{-1,0,1,0},dy{0,-1,0,1};

class Solution {
public:
   int kInversePairs(ll n, ll k) {
      vll dp(k+1);
      dp[0]=1;
      for(int i=1;i<=n;i++){
         vll ndp(k+1),pref(k+2);
         for(int j=1;j<=(k+1);j++){
            pref[j]=add(pref[j-1],dp[j-1]);
         }
         for(int j=0;j<=k;j++){
            ll p=min(i-1,j);
            ndp[j]=sub(pref[j+1],pref[j-p]);
         }
         dp=ndp;
      }
      return dp[k];
   }
};
38100