#include<bits/stdc++.h>

using namespace std;

#define int long long

const int   N   = 102;
const int   mod = 1e9 + 7;

void add(int &a,int b)  {
    a += b;
    if(a >= mod)a -= mod;
    if(a < 0)   a += mod;
}

int qpow(int a,int exp) {
    int ans = 1;
    while (exp) {
        if(exp & 1) ans = ans * a % mod;
        a = a * a % mod;  exp >>= 1;
    }
    return ans;
}

int f[N][N * N];

signed main()   {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, k;   cin >> n >> k;

    f[n + 1][0] = 1;

    int lim = 0;

    for(int i = n ; i >= 1 ; --i)   {
        for(int p = 0 ; p <= lim ; ++p)
            for(int j = 0 ; j <= k ; ++j)   {
                if(j > i)   add(f[i][p],f[i + 1][p]);
                else        add(f[i][p + (j + p) / i],f[i + 1][p]);
            }
        lim = lim + lim / i + 1;
        while(!f[i][lim])   --lim;
    }

    int ans = qpow(k + 1,n - 1) * k * (k + 1) * n / 2;
        ans %= mod;

    for(int p = 0 ; p <= lim ; ++p)
        add(ans,-p * f[1][p] % mod);

    cout << (ans + mod) % mod << endl;
}

### Prompt

Your challenge is to write 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<bits/stdc++.h>

using namespace std;

#define int long long

const int   N   = 102;
const int   mod = 1e9 + 7;

void add(int &a,int b)  {
    a += b;
    if(a >= mod)a -= mod;
    if(a < 0)   a += mod;
}

int qpow(int a,int exp) {
    int ans = 1;
    while (exp) {
        if(exp & 1) ans = ans * a % mod;
        a = a * a % mod;  exp >>= 1;
    }
    return ans;
}

int f[N][N * N];

signed main()   {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, k;   cin >> n >> k;

    f[n + 1][0] = 1;

    int lim = 0;

    for(int i = n ; i >= 1 ; --i)   {
        for(int p = 0 ; p <= lim ; ++p)
            for(int j = 0 ; j <= k ; ++j)   {
                if(j > i)   add(f[i][p],f[i + 1][p]);
                else        add(f[i][p + (j + p) / i],f[i + 1][p]);
            }
        lim = lim + lim / i + 1;
        while(!f[i][lim])   --lim;
    }

    int ans = qpow(k + 1,n - 1) * k * (k + 1) * n / 2;
        ans %= mod;

    for(int p = 0 ; p <= lim ; ++p)
        add(ans,-p * f[1][p] % mod);

    cout << (ans + mod) % mod << endl;
}

```