#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))
#define iter(v,ite) for(auto ite=(v).begin();ite!=(v).end();ite++)
#define mimunum(v,x) distance((v).begin(),lower_bound((v).begin(),(v).end(),x))

#define MOD (1000000007LL)

lli n,K;

lli dp[105][2005];



lli dat[10];

lli td[10];
lli greed(int no){
	lli res=0;
	if(no==n){
		rep(i,n)td[i]=dat[i];
		for(;;){
			bool fd=false;
			rep(i,n){
				if(td[i]==i+1){
					fd=true;
					td[i]=0;
					rep(j,i)td[j]++;
					break;
				}
			}
			if(!fd)break;
		}
		rep(i,n)res += td[i];
	}
	else{
		reg(i,0,K){
			dat[no]=i;
			res += greed(no+1);
		}
	}
	return res;
}

int nps[105]={};

lli solve(){
	//printf("%lld\n",greed(0));
	//return 0;
	
	nps[n]=0;
	ireg(i,1,n-1){
		nps[i] = 1+nps[i+1]+nps[i+1]/(i+1);
		//printf("%d %d\n",i,nps[i]);
	}
	
	//return 0;
	
	lli nk=1;
	reg(i,1,n){
		reg(p,0,nps[i]){
			lli s=0;
			reg(t,0,K){
				lli ds;
				if(i==1){
					if(t<=1){
						ds=0;
					}
					else ds=t+p;
				}
				else{
					lli tn=p;
					lli c=t+p;
					if(t<=i){
						tn += (t+p)/i;
						c = (t+p)%i;
					}
					//printf("%lld ",c);
					if(c<0 || nk<0)return -1;
					ds = ((c*nk)%MOD+dp[i-1][tn])%MOD;
					//printf("(%d %lld %lld) ",tn,c,ds);
				}
				s = (s+ds)%MOD;
			}
			dp[i][p]=s;
			//printf("%d %d : %lld\n",i,p,s);
		}
		nk = (nk*(K+1))%MOD;
	}
	
	printf("%lld\n",dp[n][0]);
	return dp[n][0];
}


int main(){
	scanf("%lld%lld",&n,&K); solve();
	/*
	reg(i,1,100){
		printf("%d\n",i);
		reg(j,1,i){
			n=i; K=j;
			if(solve()<0){
				printf("%d %d\n",n,K);
				return 0;
			}
		}
	}
	*/
	return 0;
}




### Prompt

Develop a solution in CPP to the problem described below:

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<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))
#define iter(v,ite) for(auto ite=(v).begin();ite!=(v).end();ite++)
#define mimunum(v,x) distance((v).begin(),lower_bound((v).begin(),(v).end(),x))

#define MOD (1000000007LL)

lli n,K;

lli dp[105][2005];



lli dat[10];

lli td[10];
lli greed(int no){
	lli res=0;
	if(no==n){
		rep(i,n)td[i]=dat[i];
		for(;;){
			bool fd=false;
			rep(i,n){
				if(td[i]==i+1){
					fd=true;
					td[i]=0;
					rep(j,i)td[j]++;
					break;
				}
			}
			if(!fd)break;
		}
		rep(i,n)res += td[i];
	}
	else{
		reg(i,0,K){
			dat[no]=i;
			res += greed(no+1);
		}
	}
	return res;
}

int nps[105]={};

lli solve(){
	//printf("%lld\n",greed(0));
	//return 0;
	
	nps[n]=0;
	ireg(i,1,n-1){
		nps[i] = 1+nps[i+1]+nps[i+1]/(i+1);
		//printf("%d %d\n",i,nps[i]);
	}
	
	//return 0;
	
	lli nk=1;
	reg(i,1,n){
		reg(p,0,nps[i]){
			lli s=0;
			reg(t,0,K){
				lli ds;
				if(i==1){
					if(t<=1){
						ds=0;
					}
					else ds=t+p;
				}
				else{
					lli tn=p;
					lli c=t+p;
					if(t<=i){
						tn += (t+p)/i;
						c = (t+p)%i;
					}
					//printf("%lld ",c);
					if(c<0 || nk<0)return -1;
					ds = ((c*nk)%MOD+dp[i-1][tn])%MOD;
					//printf("(%d %lld %lld) ",tn,c,ds);
				}
				s = (s+ds)%MOD;
			}
			dp[i][p]=s;
			//printf("%d %d : %lld\n",i,p,s);
		}
		nk = (nk*(K+1))%MOD;
	}
	
	printf("%lld\n",dp[n][0]);
	return dp[n][0];
}


int main(){
	scanf("%lld%lld",&n,&K); solve();
	/*
	reg(i,1,100){
		printf("%d\n",i);
		reg(j,1,i){
			n=i; K=j;
			if(solve()<0){
				printf("%d %d\n",n,K);
				return 0;
			}
		}
	}
	*/
	return 0;
}




```