//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
#include<bits/stdc++.h>
#define int long long
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
const double eps=1e-6;
const int mod=1000000007;
typedef long long ll;
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
inline string getstr(string &s,int l,int r){string ret="";for(int i=l;i<=r;i++)ret.push_back(s[i]);return ret;}
int modpow(int x,int y,int md=mod){if(y==0)return 1;int ret=modpow(x,y>>1,md);ret=(ll)ret*ret%md;if(y&1)ret=(ll)ret*x%md;return ret;}
int n,k;
inline int inv(int x){
	return modpow(x,mod-2,mod);
}
int dp[105][205*105];
int sum;
inline void add(int &x,int y){
	(x+=y)%=mod; 
}
inline void sub(int &x,int y){
	(x-=y)%=mod;(x+=mod)%=mod;
}
signed main(){
	cin>>n>>k;
	sum=n*modpow(k+1,n-1,mod)%mod*k%mod*(k+1)%mod*inv(2)%mod;
	dp[k+1][0]=1;
	for(int i=k+1;i>1;i--){
		for(int j=0;j<=200*100;j++){
			for(int v=0;v<=k;v++){
				if(v>i-1)add(dp[i-1][j],dp[i][j]);
				else add(dp[i-1][j+(j+v)/(i-1)],dp[i][j]);
			}
		}
	}
	for(int i=1;i<=200*100;i++){
		sub(sum,dp[1][i]*i%mod*modpow(k+1,n-k,mod)%mod);
	}
	cout<<sum<<endl;
	return 0;
}
### Prompt

In CPP, your task is to solve 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
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
#include<bits/stdc++.h>
#define int long long
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
const double eps=1e-6;
const int mod=1000000007;
typedef long long ll;
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
inline string getstr(string &s,int l,int r){string ret="";for(int i=l;i<=r;i++)ret.push_back(s[i]);return ret;}
int modpow(int x,int y,int md=mod){if(y==0)return 1;int ret=modpow(x,y>>1,md);ret=(ll)ret*ret%md;if(y&1)ret=(ll)ret*x%md;return ret;}
int n,k;
inline int inv(int x){
	return modpow(x,mod-2,mod);
}
int dp[105][205*105];
int sum;
inline void add(int &x,int y){
	(x+=y)%=mod; 
}
inline void sub(int &x,int y){
	(x-=y)%=mod;(x+=mod)%=mod;
}
signed main(){
	cin>>n>>k;
	sum=n*modpow(k+1,n-1,mod)%mod*k%mod*(k+1)%mod*inv(2)%mod;
	dp[k+1][0]=1;
	for(int i=k+1;i>1;i--){
		for(int j=0;j<=200*100;j++){
			for(int v=0;v<=k;v++){
				if(v>i-1)add(dp[i-1][j],dp[i][j]);
				else add(dp[i-1][j+(j+v)/(i-1)],dp[i][j]);
			}
		}
	}
	for(int i=1;i<=200*100;i++){
		sub(sum,dp[1][i]*i%mod*modpow(k+1,n-k,mod)%mod);
	}
	cout<<sum<<endl;
	return 0;
}
```