#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define pb push_back
#define mp make_pair
#define x first
#define y second

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;

template <class T>
void read(T &x)
{
	char ch;
	for (ch=getchar();(ch<'0'||ch>'9')&&ch!='-';) ch=getchar();
	x=0;int t=1;if (ch=='-') {ch=getchar();t=-1;}
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	x*=t;
}

const int mod=1000000007;
int dp[4010],dp2[4010],fac[4010];

int main()
{
	#ifndef ONLINE_JUDGE
		//freopen("input.txt","r",stdin);
		//freopen("output.txt","w",stdout);
	#endif
	int n,k;scanf("%d%d",&n,&k);
	int ans=1;
	for (int i=1;i<n;i++) ans=ll(ans)*(k+1)%mod;
	ans=ll(ans)*(k*(k+1)/2)%mod;ans=ll(ans)*n%mod;
	memset(dp,0,sizeof(dp));dp[0]=min(k+1,n);dp[1]=(k==n);
	fac[0]=1;for (int i=1;i<=n;i++) fac[i]=ll(fac[i-1])*(k+1)%mod;
	ans=((-ll(fac[n-1])*dp[1]+ans)%mod+mod)%mod;
	for (int i=n-1;i;i--)
	{
		for (int j=0;j<=4000;j++) dp2[j]=dp[j];
		memset(dp,0,sizeof(dp));
		for (int j=0;j<=4000;j++)
			if (dp2[j])
				for (int p=0;p<=k;p++)
				{
					if (p>i) {dp[j]=(dp[j]+dp2[j])%mod;continue;}
					int t=(p+j)/i;ans=((-ll(fac[i-1])*t%mod*dp2[j]+ans)%mod+mod)%mod;
					dp[t+j]=(dp[t+j]+dp2[j])%mod;
				}
	}
	printf("%d\n",ans);
	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 <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define pb push_back
#define mp make_pair
#define x first
#define y second

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;

template <class T>
void read(T &x)
{
	char ch;
	for (ch=getchar();(ch<'0'||ch>'9')&&ch!='-';) ch=getchar();
	x=0;int t=1;if (ch=='-') {ch=getchar();t=-1;}
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	x*=t;
}

const int mod=1000000007;
int dp[4010],dp2[4010],fac[4010];

int main()
{
	#ifndef ONLINE_JUDGE
		//freopen("input.txt","r",stdin);
		//freopen("output.txt","w",stdout);
	#endif
	int n,k;scanf("%d%d",&n,&k);
	int ans=1;
	for (int i=1;i<n;i++) ans=ll(ans)*(k+1)%mod;
	ans=ll(ans)*(k*(k+1)/2)%mod;ans=ll(ans)*n%mod;
	memset(dp,0,sizeof(dp));dp[0]=min(k+1,n);dp[1]=(k==n);
	fac[0]=1;for (int i=1;i<=n;i++) fac[i]=ll(fac[i-1])*(k+1)%mod;
	ans=((-ll(fac[n-1])*dp[1]+ans)%mod+mod)%mod;
	for (int i=n-1;i;i--)
	{
		for (int j=0;j<=4000;j++) dp2[j]=dp[j];
		memset(dp,0,sizeof(dp));
		for (int j=0;j<=4000;j++)
			if (dp2[j])
				for (int p=0;p<=k;p++)
				{
					if (p>i) {dp[j]=(dp[j]+dp2[j])%mod;continue;}
					int t=(p+j)/i;ans=((-ll(fac[i-1])*t%mod*dp2[j]+ans)%mod+mod)%mod;
					dp[t+j]=(dp[t+j]+dp2[j])%mod;
				}
	}
	printf("%d\n",ans);
	return 0;
}


```