#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;
const int P = 4000;
int N, K;
pair<i64, i64> dp[110][P];

void add(pair<i64, i64> &a, i64 ct, i64 pf)
{
	a = make_pair((a.first + ct) % MOD, (a.second + pf) % MOD);
}

int main()
{
	scanf("%d%d", &N, &K);

	for (int i = 0; i <= N; ++i) {
		for (int j = 0; j < P; ++j) {
			dp[i][j] = make_pair(0LL, 0LL);
		}
	}
	dp[N][0] = make_pair(1LL, 0LL);
	for (int i = N; i >= 1; --i) {
		for (int j = 0; j < P; ++j) {
			if (dp[i][j] == make_pair(0LL, 0LL)) continue;

			for (int k = 0; k <= K; ++k) {
				if (k > i) {
					add(dp[i - 1][j], dp[i][j].first, dp[i][j].second);
				} else {
					int chg = k + j;
					int j2 = j + chg / i;
					add(dp[i - 1][j2], dp[i][j].first, dp[i][j].second + dp[i][j].first * chg);
				}
			}
		}
	}
	i64 ret = 0;
	for (int i = 0; i < P; ++i) {
		ADD(ret, dp[0][i].first * i);
	}
	i64 base = K * (K + 1) / 2;
	for (int i = 0; i < N - 1; ++i) base = base * (K + 1) % MOD;
	base = base * N % MOD;

	printf("%lld\n", (base + MOD - ret) % MOD);

	return 0;
}

### Prompt

Generate 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 MOD 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;
const int P = 4000;
int N, K;
pair<i64, i64> dp[110][P];

void add(pair<i64, i64> &a, i64 ct, i64 pf)
{
	a = make_pair((a.first + ct) % MOD, (a.second + pf) % MOD);
}

int main()
{
	scanf("%d%d", &N, &K);

	for (int i = 0; i <= N; ++i) {
		for (int j = 0; j < P; ++j) {
			dp[i][j] = make_pair(0LL, 0LL);
		}
	}
	dp[N][0] = make_pair(1LL, 0LL);
	for (int i = N; i >= 1; --i) {
		for (int j = 0; j < P; ++j) {
			if (dp[i][j] == make_pair(0LL, 0LL)) continue;

			for (int k = 0; k <= K; ++k) {
				if (k > i) {
					add(dp[i - 1][j], dp[i][j].first, dp[i][j].second);
				} else {
					int chg = k + j;
					int j2 = j + chg / i;
					add(dp[i - 1][j2], dp[i][j].first, dp[i][j].second + dp[i][j].first * chg);
				}
			}
		}
	}
	i64 ret = 0;
	for (int i = 0; i < P; ++i) {
		ADD(ret, dp[0][i].first * i);
	}
	i64 base = K * (K + 1) / 2;
	for (int i = 0; i < N - 1; ++i) base = base * (K + 1) % MOD;
	base = base * N % MOD;

	printf("%lld\n", (base + MOD - ret) % MOD);

	return 0;
}

```