#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <vector>
#include <set>
#include <cassert>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <functional>
#include <iomanip>
//#include <windows.h>  //Should be deleted when using AtCoder&POJ
using namespace std;

#define ll long long
#define pii pair<int,int>
#define qi ios::sync_with_stdio(0)
/**==Info==
*Program:1
*Problem:Mancala
*Date:2019-7-3
*Algorithm:DP
*Stats:Unknown*/

bool debug=false;

int n,k;
const int mx=10000;
ll dp[105][mx];

const ll mod=1e9+7;
const ll inv2=5e8+4;

ll qp(ll a,ll b){
	if(b==0){
		return 1;
	}
	ll ans=qp(a,b/2);
	if(b%2){
		return ans*ans%mod*a%mod;
	}else{
		return ans*ans%mod;
	}
}

int main(int argc,char* argv[]){
	qi;
	cin>>n>>k;
	
	dp[n+1][0]=1;
	
//	cout<<"D"<<endl;
	
	for(int i=n;i>=1;i--){
		for(int j=0;j<mx;j++){
			for(int l=0;l<=k;l++){
//				cout<<i<<" "<<j<<" "<<l<<endl;
				
				/*
				Please, don't forget to module the answer				
				
				=====
				p71.cpp:72:23: runtime error: signed integer overflow: 6795705775047932304 + 3397852887523966152 cannot be represented in type 'long long'
				SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior p71.cpp:72:23 in 
				
				Runtime error: exit code is 1
				=====
				Used: 124 ms, 10600 KB
*/
				if(l<=i){
					//ok
					if(j+(l+j)/i<mx){
						dp[i][j+(l+j)/i]+=dp[i+1][j];
						dp[i][j+(l+j)/i]%=mod;
					}
					
				}else{
					//already (bomb)ed
					dp[i][j]+=dp[i+1][j];
					dp[i][j]%=mod;
				}
			}
		}
	}
	
//	cout<<"BBB"<<endl;
	
	ll killed=0;
	for(int i=0;i<mx;i++){
		killed+=1ll*i*dp[1][i]%mod;
		killed%=mod;
	}
//	cout<<killed<<endl;
	
	//(k+1)^(n-1)*sm*n
	ll tot=qp(k+1,n-1)*k%mod*(k+1)%mod*inv2%mod*n%mod;
	
//	cout<<tot<<endl;
	
	cout<<(tot-killed+mod)%mod<<endl;
	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 <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <vector>
#include <set>
#include <cassert>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <functional>
#include <iomanip>
//#include <windows.h>  //Should be deleted when using AtCoder&POJ
using namespace std;

#define ll long long
#define pii pair<int,int>
#define qi ios::sync_with_stdio(0)
/**==Info==
*Program:1
*Problem:Mancala
*Date:2019-7-3
*Algorithm:DP
*Stats:Unknown*/

bool debug=false;

int n,k;
const int mx=10000;
ll dp[105][mx];

const ll mod=1e9+7;
const ll inv2=5e8+4;

ll qp(ll a,ll b){
	if(b==0){
		return 1;
	}
	ll ans=qp(a,b/2);
	if(b%2){
		return ans*ans%mod*a%mod;
	}else{
		return ans*ans%mod;
	}
}

int main(int argc,char* argv[]){
	qi;
	cin>>n>>k;
	
	dp[n+1][0]=1;
	
//	cout<<"D"<<endl;
	
	for(int i=n;i>=1;i--){
		for(int j=0;j<mx;j++){
			for(int l=0;l<=k;l++){
//				cout<<i<<" "<<j<<" "<<l<<endl;
				
				/*
				Please, don't forget to module the answer				
				
				=====
				p71.cpp:72:23: runtime error: signed integer overflow: 6795705775047932304 + 3397852887523966152 cannot be represented in type 'long long'
				SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior p71.cpp:72:23 in 
				
				Runtime error: exit code is 1
				=====
				Used: 124 ms, 10600 KB
*/
				if(l<=i){
					//ok
					if(j+(l+j)/i<mx){
						dp[i][j+(l+j)/i]+=dp[i+1][j];
						dp[i][j+(l+j)/i]%=mod;
					}
					
				}else{
					//already (bomb)ed
					dp[i][j]+=dp[i+1][j];
					dp[i][j]%=mod;
				}
			}
		}
	}
	
//	cout<<"BBB"<<endl;
	
	ll killed=0;
	for(int i=0;i<mx;i++){
		killed+=1ll*i*dp[1][i]%mod;
		killed%=mod;
	}
//	cout<<killed<<endl;
	
	//(k+1)^(n-1)*sm*n
	ll tot=qp(k+1,n-1)*k%mod*(k+1)%mod*inv2%mod*n%mod;
	
//	cout<<tot<<endl;
	
	cout<<(tot-killed+mod)%mod<<endl;
	return 0;
}


```