Problem 28: Permutations with Inversions

Problem Statement: Count the number of permutations of numbers 1 through n that have exactly k inversions. Print the answer modulo 10^9+7.

Input

The first line contains two integers n and k.

Output

Print the number of such permutations modulo 10^9+7.

Examples


Input:
3 1

Output:
2

Solution Explanation

Method 1: Use dynamic programming where dp[i][j] counts the number of permutations of i elements with j inversions; update using possible positions for the ith element. Method 2: Use a generating function approach, although implementing it efficiently is more challenging compared to the DP method.

Solution in C++


#include 
#include 
using namespace std;

const int MOD = 1000000007;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k; cin >> n >> k;
    vector> dp(n+1, vector(k+1,0));
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= k; j++){
            for(int p = 0; p < i && j - p >= 0; p++){
                dp[i][j] = (dp[i][j] + dp[i-1][j-p]) % MOD;
            }
        }
    }
    cout << dp[n][k] << "
";
    return 0;
}