#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define FOR(a, b, c) for(int a = b; a <= c; ++a)
#define pb push_back
#define int long long

const int MOD = 1e9 + 7;
const int oo = 1e9;
const int N = 105;

int n, k;
int f[N][N * N], pw[N * N], cnt[N][N * N];

void upd(int &x, int y) {
    if(x == -1) x = 0ll;
    x = (x + y) % MOD;
}

signed main()
{
    //freopen("test.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    memset(f, -1, sizeof f);
    pw[0] = 1ll; FOR(i, 1, n * n) pw[i] = pw[i - 1] * (k + 1) % MOD;
    f[n + 1][0] = 0;
    cnt[n + 1][0] = 1ll;
    for(int i = n + 1; i > 1; --i) {
        // calc the tmp

        FOR(j, 0, n * n)    if(f[i][j] >= 0)    {
            if(k >= i) upd(cnt[i - 1][j], cnt[i][j] * (k - i + 1)); // case take t > i - 1
            FOR(t, 0, min(i - 1, k)) {
                int rem = (t + j) % (i - 1);
                int tim = (t + j) / (i - 1);
                upd(cnt[i - 1][tim + j], cnt[i][j]);
            }
            // calc the f[i - 1][j]
            if(k >= i) upd(f[i - 1][j], (f[i][j] * (k - i + 1) + (j * (k - i + 1) + (k - i + 1) * (k + i) / 2) * cnt[i][j]));
            FOR(t, 0, min(i - 1, k))    {
                int rem = (t + j) % (i - 1);
                int tim = (t + j) / (i - 1);
                upd(f[i - 1][tim + j], (f[i][j] + rem * cnt[i][j]) % MOD);
            }
        }
    }
    //cout << f[2][0] << ' ' << cnt[2][0] << '\n';
    int ans = 0ll;
    FOR(i, 0, n * n) if(f[1][i] >= 0) upd(ans, f[1][i]);
    cout << ans;
}

### 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
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define FOR(a, b, c) for(int a = b; a <= c; ++a)
#define pb push_back
#define int long long

const int MOD = 1e9 + 7;
const int oo = 1e9;
const int N = 105;

int n, k;
int f[N][N * N], pw[N * N], cnt[N][N * N];

void upd(int &x, int y) {
    if(x == -1) x = 0ll;
    x = (x + y) % MOD;
}

signed main()
{
    //freopen("test.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    memset(f, -1, sizeof f);
    pw[0] = 1ll; FOR(i, 1, n * n) pw[i] = pw[i - 1] * (k + 1) % MOD;
    f[n + 1][0] = 0;
    cnt[n + 1][0] = 1ll;
    for(int i = n + 1; i > 1; --i) {
        // calc the tmp

        FOR(j, 0, n * n)    if(f[i][j] >= 0)    {
            if(k >= i) upd(cnt[i - 1][j], cnt[i][j] * (k - i + 1)); // case take t > i - 1
            FOR(t, 0, min(i - 1, k)) {
                int rem = (t + j) % (i - 1);
                int tim = (t + j) / (i - 1);
                upd(cnt[i - 1][tim + j], cnt[i][j]);
            }
            // calc the f[i - 1][j]
            if(k >= i) upd(f[i - 1][j], (f[i][j] * (k - i + 1) + (j * (k - i + 1) + (k - i + 1) * (k + i) / 2) * cnt[i][j]));
            FOR(t, 0, min(i - 1, k))    {
                int rem = (t + j) % (i - 1);
                int tim = (t + j) / (i - 1);
                upd(f[i - 1][tim + j], (f[i][j] + rem * cnt[i][j]) % MOD);
            }
        }
    }
    //cout << f[2][0] << ' ' << cnt[2][0] << '\n';
    int ans = 0ll;
    FOR(i, 0, n * n) if(f[1][i] >= 0) upd(ans, f[1][i]);
    cout << ans;
}

```