#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
const ll mod = 1000000007;
ll N, K;
ll dp[102][20001];

ll beki(ll a, ll b) {
    if(b == 0) return 1;
    ll ret = beki(a, b / 2);
    ret = ret * ret % mod;
    if(b & 1) ret = ret *a % mod;
    return ret;
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    dp[N+1][0] = 1;
    for(ll i = N; i >= 1; i--) {
        ll Over = K - i;
        chmax(Over, 0LL);
        for(ll before = 0; before <= 10000; before++) {
            if(dp[i+1][before] == 0) continue;
            dp[i][before] += Over * dp[i+1][before];
            dp[i][before] %= mod;
            ll under = (i * 10000 - before) % i;
            ll carry = before / i;
            if(under == 0) under = i;
            chmin(under, min(i, K) + 1);
            //cerr << i << " " << before << " " << under << endl;
            dp[i][before+carry] += under * dp[i+1][before];
            dp[i][before+carry] %= mod;
            for(ll delta = 1; ; delta++) {
                ll New = under + delta * i;
                chmin(New, min(i, K) + 1);
                //cerr << i << " " << before << " " << delta << " " << New << " " << New - (under + (delta-1)*i) << endl;
                dp[i][before+carry+delta] += (New - (under + (delta - 1) * i)) * dp[i+1][before];
                dp[i][before+carry+delta] %= mod;
                if(New != under + delta * i) break;
            }
        }
    }
    /*
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j <= N * K; j++) {
            cerr << i << " " << j << " " << dp[i][j] << endl;
        }
    }
    */
    ll ans = beki(K + 1, N - 1) * K;
    ans %= mod;
    ans *= (K + 1);
    ans %= mod;
    ans *= beki(2, mod - 2);
    ans %= mod;
    ans *= N;
    ans %= mod;
    //cerr << ans << endl;
    for(int i = 0; i <= 10000; i++) {
        ans -= dp[1][i] * i;
        ans %= mod;
        ans += mod;
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}
### Prompt

Please provide a Cpp coded solution to the problem described below:

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;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
const ll mod = 1000000007;
ll N, K;
ll dp[102][20001];

ll beki(ll a, ll b) {
    if(b == 0) return 1;
    ll ret = beki(a, b / 2);
    ret = ret * ret % mod;
    if(b & 1) ret = ret *a % mod;
    return ret;
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    dp[N+1][0] = 1;
    for(ll i = N; i >= 1; i--) {
        ll Over = K - i;
        chmax(Over, 0LL);
        for(ll before = 0; before <= 10000; before++) {
            if(dp[i+1][before] == 0) continue;
            dp[i][before] += Over * dp[i+1][before];
            dp[i][before] %= mod;
            ll under = (i * 10000 - before) % i;
            ll carry = before / i;
            if(under == 0) under = i;
            chmin(under, min(i, K) + 1);
            //cerr << i << " " << before << " " << under << endl;
            dp[i][before+carry] += under * dp[i+1][before];
            dp[i][before+carry] %= mod;
            for(ll delta = 1; ; delta++) {
                ll New = under + delta * i;
                chmin(New, min(i, K) + 1);
                //cerr << i << " " << before << " " << delta << " " << New << " " << New - (under + (delta-1)*i) << endl;
                dp[i][before+carry+delta] += (New - (under + (delta - 1) * i)) * dp[i+1][before];
                dp[i][before+carry+delta] %= mod;
                if(New != under + delta * i) break;
            }
        }
    }
    /*
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j <= N * K; j++) {
            cerr << i << " " << j << " " << dp[i][j] << endl;
        }
    }
    */
    ll ans = beki(K + 1, N - 1) * K;
    ans %= mod;
    ans *= (K + 1);
    ans %= mod;
    ans *= beki(2, mod - 2);
    ans %= mod;
    ans *= N;
    ans %= mod;
    //cerr << ans << endl;
    for(int i = 0; i <= 10000; i++) {
        ans -= dp[1][i] * i;
        ans %= mod;
        ans += mod;
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}
```