#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <bitset>

const int MOD = 1e9 + 7;

using namespace std;

long long si = 0;

long long inq(long long a, long long b)
{
    if (b == 0) return 1;
    long long l = inq(a, b / 2);
    if (b % 2) return l * l % MOD * a % MOD;
    return l * l % MOD;
}

const int K = 4000;
vector<long long> dp(K);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            si = (si + j * inq(k + 1, n - 1)) % MOD;
        }
    }
    dp[0] = 1;
    for (int i = n; i >= 1; i--)
    {
        vector<long long> dp2(K);
        for (int a = 0; a <= k; a++)
        {
            for (int hv = 0; hv < K; hv++)
            {
                if (dp[hv] != 0)
                {
                    if (a <= i) dp2[hv + (hv + a) / i] = (dp2[hv + (hv + a) / i] + dp[hv]) % MOD;
                    else dp2[hv] = (dp2[hv] + dp[hv]) % MOD;
                }
            }
        }
        dp = dp2;
    }
    long long si2 = 0;
    for (int i = 0; i < K; i++) si2 = (si2 + dp[i] * i) % MOD;
    cout << (si + MOD - si2) % MOD;
}

### Prompt

Create a solution in cpp for 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 <vector>
#include <set>
#include <bitset>

const int MOD = 1e9 + 7;

using namespace std;

long long si = 0;

long long inq(long long a, long long b)
{
    if (b == 0) return 1;
    long long l = inq(a, b / 2);
    if (b % 2) return l * l % MOD * a % MOD;
    return l * l % MOD;
}

const int K = 4000;
vector<long long> dp(K);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            si = (si + j * inq(k + 1, n - 1)) % MOD;
        }
    }
    dp[0] = 1;
    for (int i = n; i >= 1; i--)
    {
        vector<long long> dp2(K);
        for (int a = 0; a <= k; a++)
        {
            for (int hv = 0; hv < K; hv++)
            {
                if (dp[hv] != 0)
                {
                    if (a <= i) dp2[hv + (hv + a) / i] = (dp2[hv + (hv + a) / i] + dp[hv]) % MOD;
                    else dp2[hv] = (dp2[hv] + dp[hv]) % MOD;
                }
            }
        }
        dp = dp2;
    }
    long long si2 = 0;
    for (int i = 0; i < K; i++) si2 = (si2 + dp[i] * i) % MOD;
    cout << (si + MOD - si2) % MOD;
}

```