#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 105,mo=1e9+7;
inline void add(int &x, int y){x=x+y<mo?x+y:x+y-mo;}
int n,k,f[N][N*N],mx;
int main() {
	read(n);read(k);f[n+1][0]=1;
	per(i,n,1)mx+=1+mx/i;mx+=10;
	per(i,n,1)rep(j,0,mx)if(f[i+1][j]){
		if(i<=k)f[i][j]=(f[i][j]+1LL*f[i+1][j]*(k-i))%mo;
		rep(x,0,min(i,k))add(f[i][j+(x+j)/i],f[i+1][j]);
	}
	int res=1LL*k*(k+1)/2*n%mo;rep(i,1,n-1)res=1LL*res*(k+1)%mo;
	rep(j,0,mx)res=(res-1LL*f[1][j]*j)%mo;
//	rep(j,0,mx)if(f[1][j])printf("%d:%d\n",j,f[1][j]);
	res=(res%mo+mo)%mo;cout<<res;
	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>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 105,mo=1e9+7;
inline void add(int &x, int y){x=x+y<mo?x+y:x+y-mo;}
int n,k,f[N][N*N],mx;
int main() {
	read(n);read(k);f[n+1][0]=1;
	per(i,n,1)mx+=1+mx/i;mx+=10;
	per(i,n,1)rep(j,0,mx)if(f[i+1][j]){
		if(i<=k)f[i][j]=(f[i][j]+1LL*f[i+1][j]*(k-i))%mo;
		rep(x,0,min(i,k))add(f[i][j+(x+j)/i],f[i+1][j]);
	}
	int res=1LL*k*(k+1)/2*n%mo;rep(i,1,n-1)res=1LL*res*(k+1)%mo;
	rep(j,0,mx)res=(res-1LL*f[1][j]*j)%mo;
//	rep(j,0,mx)if(f[1][j])printf("%d:%d\n",j,f[1][j]);
	res=(res%mo+mo)%mo;cout<<res;
	return 0;
}

```