#include <bits/stdc++.h>

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 b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

const int inv2 = (Mod + 1) >> 1;

const int maxn = 110;

int n, K;
int dp[maxn + 5][maxn * maxn + 5];

int main()
{
#ifdef matthew99
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	scanf("%d%d", &n, &K);
	dp[n][0] = 1;
	for (int i = n; i >= 1; --i) REP(j, 0, n * n + 1) if (dp[i][j])
	{
		REP(k, 0, K + 1)
		{
			if (k > i) (dp[i - 1][j] += dp[i][j]) %= Mod;
			else
			{
				(dp[i - 1][j + (k + j) / i] += dp[i][j]) %= Mod;
			}
		}
	}
	int ans = 1;
	REP(i, 0, n) ans = (LL)ans * (K + 1) % Mod;
	ans = (LL)ans * n % Mod * K % Mod * inv2 % Mod;
	REP(i, 0, n * n + 1) (ans -= (LL)i * dp[0][i] % Mod) %= Mod;
	(ans += Mod) %= Mod;
	printf("%d\n", ans);
	return 0;
}

### Prompt

Please create a solution in cpp 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 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 b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

const int inv2 = (Mod + 1) >> 1;

const int maxn = 110;

int n, K;
int dp[maxn + 5][maxn * maxn + 5];

int main()
{
#ifdef matthew99
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	scanf("%d%d", &n, &K);
	dp[n][0] = 1;
	for (int i = n; i >= 1; --i) REP(j, 0, n * n + 1) if (dp[i][j])
	{
		REP(k, 0, K + 1)
		{
			if (k > i) (dp[i - 1][j] += dp[i][j]) %= Mod;
			else
			{
				(dp[i - 1][j + (k + j) / i] += dp[i][j]) %= Mod;
			}
		}
	}
	int ans = 1;
	REP(i, 0, n) ans = (LL)ans * (K + 1) % Mod;
	ans = (LL)ans * n % Mod * K % Mod * inv2 % Mod;
	REP(i, 0, n * n + 1) (ans -= (LL)i * dp[0][i] % Mod) %= Mod;
	(ans += Mod) %= Mod;
	printf("%d\n", ans);
	return 0;
}

```