#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<deque>
#define ll long long
#define mp make_pair
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define r0p(i,n) for(int i=0;i<n;++i)
#pragma GCC optimize(1)
#pragma G++ optimize(1)
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#pragma GCC optimize(3)
#pragma G++ optimize(3)
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#define pii pair<int,int>
#pragma GCC diagnostic error "-std=c++11"
using namespace std;
inline void rdl(long long &val){
    long long x=0;
    int f=1;
    char ch=getchar();
    while((ch<'0' or ch>'9') and ch!='-') ch=getchar();
    if(ch=='-'){
        f=-1;
        ch=getchar();
	}
	while(ch>='0' and ch<='9'){
	    x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
    val=x*f;
}
inline void rdi(int &val){
    int x=0;
    int f=1;
    char ch=getchar();
    while((ch<'0' or ch>'9') and ch!='-') ch=getchar();
    if(ch=='-'){
        f=-1;
        ch=getchar();
    }
    while(ch>='0' and ch<='9'){
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    val=x*f;
}
inline long long rdl(){
    long long x=0;
    int f=1;
    char ch=getchar();
    while((ch<'0' or ch>'9') and ch!='-') ch=getchar();
    if(ch=='-'){
        f=-1;
        ch=getchar();
    }
    while(ch>='0' and ch<='9'){
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline int rdi(){
    int x=0;
    int f=1;
	char ch=getchar();
	while((ch<'0' or ch>'9') and ch!='-') ch=getchar();
	if(ch=='-'){
        f=-1;
        ch=getchar();
    }
    while(ch>='0' and ch<='9'){
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline void _write(int x){
	write(x);
	putchar(' ');
}
inline void print(int x){
	write(x);
	putchar('\n');
}
inline void write(ll x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline void _write(ll x){
	write(x);
	putchar(' ');
}
inline void print(ll x){
	write(x);
	putchar('\n');
}
pair<ll,ll> dp[111][4444];
int n,k;
const ll md=1000000007;
inline void addpair(pair<ll,ll>&a,pair<ll,ll> p){
	a.first+=p.first;
	a.second+=p.second;
	if(a.first>=md) a.first-=md;
	if(a.second>=md) a.second-=md;
}
inline void muladdpair(pair<ll,ll>&a,ll x,ll y){
	a.first=(a.first+x)%md;
	a.second=(a.second+y)%md;
}
inline void add(ll &x,ll y){x+=y;if(x>=md) x-=md;}
inline void muladd(ll &x,ll y){x=(x+y)%md;}
inline ll qp(ll a,ll b){
	ll rt=1;
	while(b){
		if(b&1) rt=(rt*a)%md;
		a=(a*a)%md;
		b>>=1;
	}
	return rt;
}
int main(){
	rdi(n),rdi(k);
	int i,j,f;
	dp[n][0]=mp(1ll,0ll);
	for(i=n;i;--i){
		for(j=0;j<4000;++j){
			if(dp[i][j]==mp(0ll,0ll)) continue;
			for(f=0;f<=k;++f){
				if(f>i){
					addpair(dp[i-1][j],dp[i][j]);
				}else{
					ll cg=f+j,tj=j+cg/i;
					muladdpair(dp[i-1][tj],dp[i][j].first,dp[i][j].second+dp[i][j].first*cg);
				}
			}
		}
	}
	ll ans=0;
	for(i=0;i<4000;++i) muladd(ans,dp[0][i].first*i);
	ll base=k*(k+1)/2;
	base=(base*qp(k+1,n-1))%md*n%md;
	print((base+md-ans)%md);
}
### 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
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<deque>
#define ll long long
#define mp make_pair
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define r0p(i,n) for(int i=0;i<n;++i)
#pragma GCC optimize(1)
#pragma G++ optimize(1)
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#pragma GCC optimize(3)
#pragma G++ optimize(3)
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#define pii pair<int,int>
#pragma GCC diagnostic error "-std=c++11"
using namespace std;
inline void rdl(long long &val){
    long long x=0;
    int f=1;
    char ch=getchar();
    while((ch<'0' or ch>'9') and ch!='-') ch=getchar();
    if(ch=='-'){
        f=-1;
        ch=getchar();
	}
	while(ch>='0' and ch<='9'){
	    x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
    val=x*f;
}
inline void rdi(int &val){
    int x=0;
    int f=1;
    char ch=getchar();
    while((ch<'0' or ch>'9') and ch!='-') ch=getchar();
    if(ch=='-'){
        f=-1;
        ch=getchar();
    }
    while(ch>='0' and ch<='9'){
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    val=x*f;
}
inline long long rdl(){
    long long x=0;
    int f=1;
    char ch=getchar();
    while((ch<'0' or ch>'9') and ch!='-') ch=getchar();
    if(ch=='-'){
        f=-1;
        ch=getchar();
    }
    while(ch>='0' and ch<='9'){
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline int rdi(){
    int x=0;
    int f=1;
	char ch=getchar();
	while((ch<'0' or ch>'9') and ch!='-') ch=getchar();
	if(ch=='-'){
        f=-1;
        ch=getchar();
    }
    while(ch>='0' and ch<='9'){
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline void _write(int x){
	write(x);
	putchar(' ');
}
inline void print(int x){
	write(x);
	putchar('\n');
}
inline void write(ll x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline void _write(ll x){
	write(x);
	putchar(' ');
}
inline void print(ll x){
	write(x);
	putchar('\n');
}
pair<ll,ll> dp[111][4444];
int n,k;
const ll md=1000000007;
inline void addpair(pair<ll,ll>&a,pair<ll,ll> p){
	a.first+=p.first;
	a.second+=p.second;
	if(a.first>=md) a.first-=md;
	if(a.second>=md) a.second-=md;
}
inline void muladdpair(pair<ll,ll>&a,ll x,ll y){
	a.first=(a.first+x)%md;
	a.second=(a.second+y)%md;
}
inline void add(ll &x,ll y){x+=y;if(x>=md) x-=md;}
inline void muladd(ll &x,ll y){x=(x+y)%md;}
inline ll qp(ll a,ll b){
	ll rt=1;
	while(b){
		if(b&1) rt=(rt*a)%md;
		a=(a*a)%md;
		b>>=1;
	}
	return rt;
}
int main(){
	rdi(n),rdi(k);
	int i,j,f;
	dp[n][0]=mp(1ll,0ll);
	for(i=n;i;--i){
		for(j=0;j<4000;++j){
			if(dp[i][j]==mp(0ll,0ll)) continue;
			for(f=0;f<=k;++f){
				if(f>i){
					addpair(dp[i-1][j],dp[i][j]);
				}else{
					ll cg=f+j,tj=j+cg/i;
					muladdpair(dp[i-1][tj],dp[i][j].first,dp[i][j].second+dp[i][j].first*cg);
				}
			}
		}
	}
	ll ans=0;
	for(i=0;i<4000;++i) muladd(ans,dp[0][i].first*i);
	ll base=k*(k+1)/2;
	base=(base*qp(k+1,n-1))%md*n%md;
	print((base+md-ans)%md);
}
```