#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#define Endl endl
#define mp make_pair
#define ll long long 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define ceil(a,b) ((a-1)/b+1)
#define srand() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l,r) uniform_int_distribution<int>(l,r)(rng)
typedef unsigned long long ull;
const int inf=1039074182;
using namespace std;
int n,k;
int dp[105][10005];

namespace combinatorics
{
	int *fac;
	int *ifac;
	int mod;
	inline int add(int a,int b)
	{
		return (a+b)%mod;
	}
	inline int minus(int a,int b)
	{
		return (a-b+mod)%mod;
	}
	inline int mutiply(int a,int b)
	{
		return (1LL*a*b)%mod;
	}
	inline int fastpow(int basic,int x)
	{
		int res=1;
		while(x)
		{
			if(x&1)	res=mutiply(res,basic);
			basic=mutiply(basic,basic);
			x>>=1;
		}
		return res;
	}
	inline int inv(int x)
	{
		return fastpow(x,mod-2);
	}
	void init(int n,int tmod)
	{
		mod=tmod;
		fac=new int[n+5];
		ifac=new int[n+5];
		fac[0]=1;
		for(int i=1;i<=n;i++)
		{
			fac[i]=mutiply(fac[i-1],i);
		}
		ifac[n]=inv(fac[n]);
		for(int i=n-1;i>=0;i--)
		{
			ifac[i]=mutiply(ifac[i+1],i+1);
		}
	}
	inline int C(int n,int m)
	{
		return mutiply(mutiply(fac[n],ifac[m]),ifac[n-m]);
	}
};
using namespace combinatorics;
int main()
{
//	freopen("input.txt","r",stdin);
	cin>>n>>k;
	init(n,1e9+7);
	dp[n][0]=1;
	int res=mutiply(n,mutiply(k,mutiply(inv(2),fastpow(k+1,n))));
	for(int i=n;i>=1;i--)
	{
		for(int j=0;j<=k*(n-i);j++)
		{
			for(int put=0;put<=k;put++)
			{
				if(put<=i)
				{
					dp[i-1][j+(put+j)/i]=add(dp[i-1][j+(put+j)/i],dp[i][j]);
				}
				else
				{
					dp[i-1][j]=add(dp[i-1][j],dp[i][j]);
				}
			}
		}
	}
	for(int i=0;i<=n*k;i++)
	{
		res=combinatorics::minus(res,mutiply(dp[0][i],i));
	}
	cout<<res<<endl;
	return 0;
}
### Prompt

Please formulate a Cpp solution to 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 <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#define Endl endl
#define mp make_pair
#define ll long long 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define ceil(a,b) ((a-1)/b+1)
#define srand() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l,r) uniform_int_distribution<int>(l,r)(rng)
typedef unsigned long long ull;
const int inf=1039074182;
using namespace std;
int n,k;
int dp[105][10005];

namespace combinatorics
{
	int *fac;
	int *ifac;
	int mod;
	inline int add(int a,int b)
	{
		return (a+b)%mod;
	}
	inline int minus(int a,int b)
	{
		return (a-b+mod)%mod;
	}
	inline int mutiply(int a,int b)
	{
		return (1LL*a*b)%mod;
	}
	inline int fastpow(int basic,int x)
	{
		int res=1;
		while(x)
		{
			if(x&1)	res=mutiply(res,basic);
			basic=mutiply(basic,basic);
			x>>=1;
		}
		return res;
	}
	inline int inv(int x)
	{
		return fastpow(x,mod-2);
	}
	void init(int n,int tmod)
	{
		mod=tmod;
		fac=new int[n+5];
		ifac=new int[n+5];
		fac[0]=1;
		for(int i=1;i<=n;i++)
		{
			fac[i]=mutiply(fac[i-1],i);
		}
		ifac[n]=inv(fac[n]);
		for(int i=n-1;i>=0;i--)
		{
			ifac[i]=mutiply(ifac[i+1],i+1);
		}
	}
	inline int C(int n,int m)
	{
		return mutiply(mutiply(fac[n],ifac[m]),ifac[n-m]);
	}
};
using namespace combinatorics;
int main()
{
//	freopen("input.txt","r",stdin);
	cin>>n>>k;
	init(n,1e9+7);
	dp[n][0]=1;
	int res=mutiply(n,mutiply(k,mutiply(inv(2),fastpow(k+1,n))));
	for(int i=n;i>=1;i--)
	{
		for(int j=0;j<=k*(n-i);j++)
		{
			for(int put=0;put<=k;put++)
			{
				if(put<=i)
				{
					dp[i-1][j+(put+j)/i]=add(dp[i-1][j+(put+j)/i],dp[i][j]);
				}
				else
				{
					dp[i-1][j]=add(dp[i-1][j],dp[i][j]);
				}
			}
		}
	}
	for(int i=0;i<=n*k;i++)
	{
		res=combinatorics::minus(res,mutiply(dp[0][i],i));
	}
	cout<<res<<endl;
	return 0;
}
```