// https://cf17-final.contest.atcoder.jp/tasks/cf17_final_e
#include<iostream>
#include<vector>
#include<unordered_map>

#ifdef _GLIBCXX_DEBUG
#define cin cin_
#include<sstream>
namespace std{std::stringstream cin(R"(
20 17
)");}
#endif

int k; // maximum value of an element
int MOD=1000000007;
std::vector<int> kp1_xp;

std::vector<std::unordered_map<int,int>> g_mem;
int g(int p,int e){
	if(p==1){
		return (
			// if a[1]==0
			e +
			// if a[1]==1
			(e+1)
		)%MOD;
	}

	auto it=g_mem[p].find(e);
	if(it!=g_mem[p].end())return it->second;

	int ans=0;
	for(int i=0;i<=k;++i){
		// i = a[p]
		if(i>p){
			ans=(ans+g(p-1,e))%MOD; // this can be optimized?
		}else{
			int nStep=(i+e)/p;
			ans=(ans+g(p-1,e+nStep)+nStep*(int64_t)kp1_xp[p-1])%MOD;
		}
	}

	g_mem[p].emplace(e,ans);
	return ans;
}

int main(){
	std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
	int n;std::cin>>n>>k;

	// init kp1_xp (kp1_xp[x] = (k+1)**x %MOD)
	kp1_xp.resize(n+1);
	kp1_xp[0]=1;
	for(int i=1;i<=n;++i)
		kp1_xp[i]=int64_t(k+1)*kp1_xp[i-1]%MOD;

	int sum_all=k*int64_t(k+1)/2 %MOD *kp1_xp[n-1] %MOD *n %MOD;
	// avg each position: k/2, n. of seq: (k+1)**n, n. of pos: n

	g_mem.resize(n+1);
	std::cout<<(sum_all+MOD-g(n,0))%MOD<<std::endl;
}

### Prompt

Please formulate 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
// https://cf17-final.contest.atcoder.jp/tasks/cf17_final_e
#include<iostream>
#include<vector>
#include<unordered_map>

#ifdef _GLIBCXX_DEBUG
#define cin cin_
#include<sstream>
namespace std{std::stringstream cin(R"(
20 17
)");}
#endif

int k; // maximum value of an element
int MOD=1000000007;
std::vector<int> kp1_xp;

std::vector<std::unordered_map<int,int>> g_mem;
int g(int p,int e){
	if(p==1){
		return (
			// if a[1]==0
			e +
			// if a[1]==1
			(e+1)
		)%MOD;
	}

	auto it=g_mem[p].find(e);
	if(it!=g_mem[p].end())return it->second;

	int ans=0;
	for(int i=0;i<=k;++i){
		// i = a[p]
		if(i>p){
			ans=(ans+g(p-1,e))%MOD; // this can be optimized?
		}else{
			int nStep=(i+e)/p;
			ans=(ans+g(p-1,e+nStep)+nStep*(int64_t)kp1_xp[p-1])%MOD;
		}
	}

	g_mem[p].emplace(e,ans);
	return ans;
}

int main(){
	std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
	int n;std::cin>>n>>k;

	// init kp1_xp (kp1_xp[x] = (k+1)**x %MOD)
	kp1_xp.resize(n+1);
	kp1_xp[0]=1;
	for(int i=1;i<=n;++i)
		kp1_xp[i]=int64_t(k+1)*kp1_xp[i-1]%MOD;

	int sum_all=k*int64_t(k+1)/2 %MOD *kp1_xp[n-1] %MOD *n %MOD;
	// avg each position: k/2, n. of seq: (k+1)**n, n. of pos: n

	g_mem.resize(n+1);
	std::cout<<(sum_all+MOD-g(n,0))%MOD<<std::endl;
}

```