#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

#define ANS(f) if(f) cout << "YES" << endl; else cout << "NO" << endl;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }
void debug(mat m){REP(i, m.size()){ REP(j, m[0].size()){ cout << m[i][j] << ","; } cout << endl; }}

int modpow(int x, int n, int m){
    int a = 1;
    IREP(i, 64){
        a = (a * a) % m;
        if(((n >> i) & 1) == 1) a = (a * x) % m;
    }
    return a;
}

#define M 3300
signed main(){

    int N, K; cin >> N >> K;
    int mod = 1000000007;

    mat dp(N + 1, vec(M + 1, 0));
    if(K >= N) dp[N][1] = 1;
    dp[N][0] = K + 1 - dp[N][1];
    IFOR(i, 1, N){
        int d = K - i;
        if(d > 0) REP(j, M + 1){
            dp[i][j] += d * dp[i + 1][j];
            dp[i][j] %= mod;
        }
        REP(a, min(K, i) + 1){
            REP(j, M + 1){
                int s = j + (a + j) / i;
                if(s <= M){
                    dp[i][s] += dp[i + 1][j];
                    dp[i][s] %= mod;
                }
            }
        }
    }
    //debug(dp);
    
    int ans = (K * (K + 1) / 2 * N * modpow(K + 1, N - 1, mod)) % mod;;
    //cout << ans << endl;
    REP(i, M + 1){
        ans -= i * dp[1][i];
        ans = (ans % mod + mod) % mod; 
    }

    cout << ans << endl;
    
    return 0;
}
### Prompt

Please formulate 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>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define int long long
#define INF 1000000000000000000
using namespace std;

#define ANS(f) if(f) cout << "YES" << endl; else cout << "NO" << endl;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

template<typename T>
void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readi(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }
void debug(mat m){REP(i, m.size()){ REP(j, m[0].size()){ cout << m[i][j] << ","; } cout << endl; }}

int modpow(int x, int n, int m){
    int a = 1;
    IREP(i, 64){
        a = (a * a) % m;
        if(((n >> i) & 1) == 1) a = (a * x) % m;
    }
    return a;
}

#define M 3300
signed main(){

    int N, K; cin >> N >> K;
    int mod = 1000000007;

    mat dp(N + 1, vec(M + 1, 0));
    if(K >= N) dp[N][1] = 1;
    dp[N][0] = K + 1 - dp[N][1];
    IFOR(i, 1, N){
        int d = K - i;
        if(d > 0) REP(j, M + 1){
            dp[i][j] += d * dp[i + 1][j];
            dp[i][j] %= mod;
        }
        REP(a, min(K, i) + 1){
            REP(j, M + 1){
                int s = j + (a + j) / i;
                if(s <= M){
                    dp[i][s] += dp[i + 1][j];
                    dp[i][s] %= mod;
                }
            }
        }
    }
    //debug(dp);
    
    int ans = (K * (K + 1) / 2 * N * modpow(K + 1, N - 1, mod)) % mod;;
    //cout << ans << endl;
    REP(i, M + 1){
        ans -= i * dp[1][i];
        ans = (ans % mod + mod) % mod; 
    }

    cout << ans << endl;
    
    return 0;
}
```