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

const int N = 105;
const int M = 10001;
const int md = 1e9 + 7;

void add(int &x, int y) { x += y; while(x >= md) x -= md; if (x < 0) x += md; }

int n, k;
int f[N][M];
int pw[N];
int ans;

int main() {
	scanf("%d %d", &n, &k);
	pw[0] = 1; for (int i = 1; i < N; ++i) pw[i] = 1LL * pw[i-1] * (k + 1) % md;
	f[n + 1][0] = 1;
	for (int i = n; i >= 1; --i) {
		for (int j = 0; j < M; ++j) if (f[i + 1][j]) {
			for (int t = 0; t <= k; ++t) {
				int cur = (t <= i ? (t + j) / i : 0);
				add(f[i][j + cur], f[i + 1][j]);
				add(ans, 1LL * (1LL * f[i + 1][j] * pw[i - 1] % md) * (t - cur) % md);
			}
		}
 	}

 	printf("%d\n", ans);
}
### Prompt

Create a solution in CPP for 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;

const int N = 105;
const int M = 10001;
const int md = 1e9 + 7;

void add(int &x, int y) { x += y; while(x >= md) x -= md; if (x < 0) x += md; }

int n, k;
int f[N][M];
int pw[N];
int ans;

int main() {
	scanf("%d %d", &n, &k);
	pw[0] = 1; for (int i = 1; i < N; ++i) pw[i] = 1LL * pw[i-1] * (k + 1) % md;
	f[n + 1][0] = 1;
	for (int i = n; i >= 1; --i) {
		for (int j = 0; j < M; ++j) if (f[i + 1][j]) {
			for (int t = 0; t <= k; ++t) {
				int cur = (t <= i ? (t + j) / i : 0);
				add(f[i][j + cur], f[i + 1][j]);
				add(ans, 1LL * (1LL * f[i + 1][j] * pw[i - 1] % md) * (t - cur) % md);
			}
		}
 	}

 	printf("%d\n", ans);
}
```