// In the name of God

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>

using namespace std;

#define rep(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline bool smin(T &a, const T &b)   { return a > b ? a = b : a;    }
template<typename T> inline bool smax(T &a, const T &b)   { return a < b ? a = b : a;    }

typedef long long LL;

const int N = (int) 105, mod = (int) 1e9 + 7;
int dp[N * N], odp[N * N];
void sadd(int &x, int y) {
	x += y;
	while (x >= mod) x -= mod;
}
int main() {
	int n, k;
	cin >> n >> k;
	int sum_all = n * (k + 1) * k / 2;
	for (int x = 0; x < n - 1; ++x) sum_all = sum_all * (LL) (k + 1) % mod;
	dp[0] = 1;
	for (int pl = n - 1; pl >= 0; --pl) {
		memcpy(odp, dp, sizeof dp);
		memset(dp, 0, sizeof dp);
		for (int val = 0; val <= k; ++val) {
			if (val > pl + 1) {
				for (int j = 0; j < N * N; ++j) if (odp[j]) sadd(dp[j], odp[j]);	
			} else {
				for (int j = 0; j < N * N; ++j)	if (odp[j]) {
					int fin_val = j + val;
					int add = fin_val / (pl + 1);
					sadd(dp[j + add], odp[j]);
				}
			}
		}
	}
	for (int j = 0; j < N * N; ++j) if (dp[j]) {
		sum_all = (sum_all - dp[j] * (LL) j % mod + mod) % mod;
	}
	cout << sum_all << endl;
}





### Prompt

Your challenge is to write 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
// In the name of God

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>

using namespace std;

#define rep(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline bool smin(T &a, const T &b)   { return a > b ? a = b : a;    }
template<typename T> inline bool smax(T &a, const T &b)   { return a < b ? a = b : a;    }

typedef long long LL;

const int N = (int) 105, mod = (int) 1e9 + 7;
int dp[N * N], odp[N * N];
void sadd(int &x, int y) {
	x += y;
	while (x >= mod) x -= mod;
}
int main() {
	int n, k;
	cin >> n >> k;
	int sum_all = n * (k + 1) * k / 2;
	for (int x = 0; x < n - 1; ++x) sum_all = sum_all * (LL) (k + 1) % mod;
	dp[0] = 1;
	for (int pl = n - 1; pl >= 0; --pl) {
		memcpy(odp, dp, sizeof dp);
		memset(dp, 0, sizeof dp);
		for (int val = 0; val <= k; ++val) {
			if (val > pl + 1) {
				for (int j = 0; j < N * N; ++j) if (odp[j]) sadd(dp[j], odp[j]);	
			} else {
				for (int j = 0; j < N * N; ++j)	if (odp[j]) {
					int fin_val = j + val;
					int add = fin_val / (pl + 1);
					sadd(dp[j + add], odp[j]);
				}
			}
		}
	}
	for (int j = 0; j < N * N; ++j) if (dp[j]) {
		sum_all = (sum_all - dp[j] * (LL) j % mod + mod) % mod;
	}
	cout << sum_all << endl;
}





```