#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
typedef complex<ld> Point;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
const ld eps = 1e-6;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;

//3281

const int mn = 3334;
//num
ll dp1[101][mn];
//sum
ll dp2[101][mn];
void solve() {
	int n, m; cin >> n >> m;
	dp1[0][0] = 1;
	rep(i, n) {
		int c = n - i;
		rep(j, mn) {
			if (dp1[i][j] == 0)continue;
			rep(k, m + 1) {
				if (k > c) {
					dp1[i + 1][j] += dp1[i][j];
					if (dp1[i + 1][j] >= mod)dp1[i + 1][j] -= mod;
					dp2[i + 1][j] = (dp2[i + 1][j] + dp2[i][j]+dp1[i][j] * k) % mod;
				}
				else {
					int z = j + k;
					int d = z / c;
					dp1[i + 1][d+j] += dp1[i][j];
					if (dp1[i + 1][d + j] >= mod)dp1[i + 1][d + j] -= mod;
					dp2[i + 1][d + j] = (dp2[i + 1][d + j] + dp2[i][j] + dp1[i][j] * k) % mod;
				}
			}
		}
	}
	ll ans = 0;
	rep(i, mn) {
		ll csum = dp2[n][i] - dp1[n][i] * i;
		csum = (csum%mod + mod) % mod;
		ans = (ans + csum) % mod;
	}
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	//stop
	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<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
typedef complex<ld> Point;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
const ld eps = 1e-6;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;

//3281

const int mn = 3334;
//num
ll dp1[101][mn];
//sum
ll dp2[101][mn];
void solve() {
	int n, m; cin >> n >> m;
	dp1[0][0] = 1;
	rep(i, n) {
		int c = n - i;
		rep(j, mn) {
			if (dp1[i][j] == 0)continue;
			rep(k, m + 1) {
				if (k > c) {
					dp1[i + 1][j] += dp1[i][j];
					if (dp1[i + 1][j] >= mod)dp1[i + 1][j] -= mod;
					dp2[i + 1][j] = (dp2[i + 1][j] + dp2[i][j]+dp1[i][j] * k) % mod;
				}
				else {
					int z = j + k;
					int d = z / c;
					dp1[i + 1][d+j] += dp1[i][j];
					if (dp1[i + 1][d + j] >= mod)dp1[i + 1][d + j] -= mod;
					dp2[i + 1][d + j] = (dp2[i + 1][d + j] + dp2[i][j] + dp1[i][j] * k) % mod;
				}
			}
		}
	}
	ll ans = 0;
	rep(i, mn) {
		ll csum = dp2[n][i] - dp1[n][i] * i;
		csum = (csum%mod + mod) % mod;
		ans = (ans + csum) % mod;
	}
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	//stop
	return 0;
}
```