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

const int MOD = 1e9 + 7;

long long MyPow(long long x, long long y) {
	long long c = 1;
	while(y) {
		if(y & 1) c = c * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return c;
}

int n, k;
long long f[200][20000];

void U(long long &x) {
	if(x > MOD) x -= MOD;
	if(x < 0) x += MOD;
}

int main(void) {
	scanf("%d%d", &n, &k);
	long long ans = 0, pp = MyPow(k + 1, n - 1);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= k; j++)
			ans = (ans + pp * j) % MOD;
	}
	f[n][0] = 1;
	for(int i = n; i; i--) {
		for(int j = 0; j <= 10000; j++) {
			if(!f[i][j]) continue;
			for(int l = 0; l <= k; l++) {
				if(l <= i) 
					U(f[i - 1][j + (l + j) / i] += f[i][j] % MOD);
				else 
					U(f[i - 1][j] += f[i][j]);
			}
		}
	}
	for(int i = 0; i <= 10000; i++)
		U(ans -= i * f[0][i] % MOD);
		printf("%lld\n", ans);
	return 0;
}








### Prompt

Construct a CPP code solution to the problem outlined:

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 MOD = 1e9 + 7;

long long MyPow(long long x, long long y) {
	long long c = 1;
	while(y) {
		if(y & 1) c = c * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return c;
}

int n, k;
long long f[200][20000];

void U(long long &x) {
	if(x > MOD) x -= MOD;
	if(x < 0) x += MOD;
}

int main(void) {
	scanf("%d%d", &n, &k);
	long long ans = 0, pp = MyPow(k + 1, n - 1);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= k; j++)
			ans = (ans + pp * j) % MOD;
	}
	f[n][0] = 1;
	for(int i = n; i; i--) {
		for(int j = 0; j <= 10000; j++) {
			if(!f[i][j]) continue;
			for(int l = 0; l <= k; l++) {
				if(l <= i) 
					U(f[i - 1][j + (l + j) / i] += f[i][j] % MOD);
				else 
					U(f[i - 1][j] += f[i][j]);
			}
		}
	}
	for(int i = 0; i <= 10000; i++)
		U(ans -= i * f[0][i] % MOD);
		printf("%lld\n", ans);
	return 0;
}








```