//In the name of God
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 120;
const ll maxm = 3400;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second

ll n, k, dp[maxn][maxm], ans;

int main(){
    fast_io;

    cin >> n >> k;
    ans = n * k * 500000004 % mod;
    dp[n + 1][0] = 1;
    for(ll i = n; i > 0; i--){
        for(ll j = 0; j <= k; j++){
            for(ll o = 0; o < maxm; o++){
                if(j > i){
                    dp[i][o] += dp[i + 1][o];
                    if(dp[i][o] >= mod) dp[i][o] -= mod;
                }
                else if(o + (o + j) / i < maxm){
                    dp[i][o + (o + j) / i] += dp[i + 1][o];
                    if(dp[i][o + (o + j) / i] >= mod) dp[i][o + (o + j) / i] -= mod;
                }
            }
        }
        ans = ans * (k + 1) % mod;
    }
    for(ll i = 0; i < maxm; i++){
        ans = (ans - i * dp[1][i]) % mod;
    }
    cout << (ans + mod) % mod;

    return 0;
}

### Prompt

Your task is to create a CPP solution to the following problem:

Consider the following game:

* The game is played using a row of N squares and many stones.
* First, a_i stones are put in Square i\ (1 \leq i \leq N).
* A player can perform the following operation as many time as desired: "Select an integer i such that Square i contains exactly i stones. Remove all the stones from Square i, and add one stone to each of the i-1 squares from Square 1 to Square i-1."
* The final score of the player is the total number of the stones remaining in the squares.



For a sequence a of length N, let f(a) be the minimum score that can be obtained when the game is played on a.

Find the sum of f(a) over all sequences a of length N where each element is between 0 and K (inclusive). Since it can be extremely large, find the answer modulo 1000000007 (= 10^9+7).

Constraints

* 1 \leq N \leq 100
* 1 \leq K \leq N

Input

Input is given from Standard Input in the following format:


N K


Output

Print the sum of f(a) modulo 1000000007 (= 10^9+7).

Examples

Input

2 2


Output

10


Input

20 17


Output

983853488

### Response

```cpp
//In the name of God
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 120;
const ll maxm = 3400;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second

ll n, k, dp[maxn][maxm], ans;

int main(){
    fast_io;

    cin >> n >> k;
    ans = n * k * 500000004 % mod;
    dp[n + 1][0] = 1;
    for(ll i = n; i > 0; i--){
        for(ll j = 0; j <= k; j++){
            for(ll o = 0; o < maxm; o++){
                if(j > i){
                    dp[i][o] += dp[i + 1][o];
                    if(dp[i][o] >= mod) dp[i][o] -= mod;
                }
                else if(o + (o + j) / i < maxm){
                    dp[i][o + (o + j) / i] += dp[i + 1][o];
                    if(dp[i][o + (o + j) / i] >= mod) dp[i][o + (o + j) / i] -= mod;
                }
            }
        }
        ans = ans * (k + 1) % mod;
    }
    for(ll i = 0; i < maxm; i++){
        ans = (ans - i * dp[1][i]) % mod;
    }
    cout << (ans + mod) % mod;

    return 0;
}

```