#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <numeric>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long int int64;


const int MOD = (int) 1e9 + 7;
void sadd(int &a, int b)
{
    a += b;
    if (a >= MOD) a -= MOD;
}
void ssub(int &a, int b)
{
    a -= b;
    if (a < 0) a += MOD;
}
int add(int a, int b)
{
    sadd(a, b);
    return a;
}
int mul(int a, int b)
{
    return (a * 1LL * b) % MOD;
}

const int K = (int) 5000; 
int dp[2][K];
const int N = 105;
int cnt[N];

int main(int,  char **)
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

    int n, k;
    scanf("%d%d", &n, &k);

    memset(dp, 0, sizeof dp);
    int t = 0, nt = 1;
    dp[t][0] = 1;

    int sum = 0;
    for (int i = 1; i <= k; i++)
        sadd(sum, i);

    cnt[0] = 1;
    
    for (int i = 0; i < n; i++)
        cnt[i + 1] = mul(cnt[i], k + 1);
    int ans = mul(cnt[n - 1], mul(sum, n) );
    eprintf("ans = %d\n", ans);

    for (int i = n; i >= 1; i--)
    {
        memset(dp[nt], 0, sizeof dp[nt] );

        for (int j = 0; j < K; j++)
        {
            int cur = dp[t][j];
            if (cur == 0) continue;
            int big = max(0, k - i);
            sadd(dp[nt][j], mul(cur, big) );
            for (int val = 0; val <= min(k, i); val++)
            {
                int nx = j + (val + j) / i;
                if (nx >= K)
                {
                    eprintf("i = %d, nx = %d\n", i, nx);
                    throw;
                }
                sadd(dp[nt][nx], cur);
            }
        }

        swap(t, nt);
//        for (int it = 0; it < 10; it++)
//            eprintf("%d ", dp[t][it] );
//        eprintf("\n");
    }


    for (int i = 0; i < K; i++)
        ssub(ans, mul(dp[t][i], i) );

    printf("%d\n", ans);


	return 0;
}


### Prompt

Your task is to create 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 <vector>
#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <numeric>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long int int64;


const int MOD = (int) 1e9 + 7;
void sadd(int &a, int b)
{
    a += b;
    if (a >= MOD) a -= MOD;
}
void ssub(int &a, int b)
{
    a -= b;
    if (a < 0) a += MOD;
}
int add(int a, int b)
{
    sadd(a, b);
    return a;
}
int mul(int a, int b)
{
    return (a * 1LL * b) % MOD;
}

const int K = (int) 5000; 
int dp[2][K];
const int N = 105;
int cnt[N];

int main(int,  char **)
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

    int n, k;
    scanf("%d%d", &n, &k);

    memset(dp, 0, sizeof dp);
    int t = 0, nt = 1;
    dp[t][0] = 1;

    int sum = 0;
    for (int i = 1; i <= k; i++)
        sadd(sum, i);

    cnt[0] = 1;
    
    for (int i = 0; i < n; i++)
        cnt[i + 1] = mul(cnt[i], k + 1);
    int ans = mul(cnt[n - 1], mul(sum, n) );
    eprintf("ans = %d\n", ans);

    for (int i = n; i >= 1; i--)
    {
        memset(dp[nt], 0, sizeof dp[nt] );

        for (int j = 0; j < K; j++)
        {
            int cur = dp[t][j];
            if (cur == 0) continue;
            int big = max(0, k - i);
            sadd(dp[nt][j], mul(cur, big) );
            for (int val = 0; val <= min(k, i); val++)
            {
                int nx = j + (val + j) / i;
                if (nx >= K)
                {
                    eprintf("i = %d, nx = %d\n", i, nx);
                    throw;
                }
                sadd(dp[nt][nx], cur);
            }
        }

        swap(t, nt);
//        for (int it = 0; it < 10; it++)
//            eprintf("%d ", dp[t][it] );
//        eprintf("\n");
    }


    for (int i = 0; i < K; i++)
        ssub(ans, mul(dp[t][i], i) );

    printf("%d\n", ans);


	return 0;
}


```