// ※※※ 解答不能 ※※※
// yokozuna57氏.
// https://atcoder.jp/contests/cf17-final/submissions/1805242
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MOD = 1e9 + 7;
#define repx(i, a, b) for(LL i = a; i < b; i++)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(LL i = a; i >= b; i--)
LL dp[111][5050];

LL mPow(LL x, LL k){
    if(k == 0) return 1;
    LL ret = mPow(x, k / 2);
    ret *= ret;
    ret %= MOD;
    if(k % 2 == 1){
        ret *= x;
        ret %= MOD;
    }
    return ret;
}

int main(){
    LL N, K;
    scanf("%lld %lld", &N, &K);
    dp[K][0] = K;
    dp[K][1] = 1;
    repr(i, K - 1, 1){
        rep(j, 5050){
            dp[i][j] += dp[i + 1][j] * (K - i);
            dp[i][j + j / i] += dp[i + 1][j] * (i - j % i);
            dp[i][j + j / i + 1] += dp[i + 1][j] * (j % i + 1);
        }
        rep(j, 5050) dp[i][j] %= MOD;
    }
    
    LL ret = mPow(K + 1, K) * N * K;
    ret %= MOD;
    ret *= mPow(2, MOD - 2);
    ret %= MOD;
    repx(i, 1, 5049){
        dp[1][i] *= i;
        dp[1][i] %= MOD;
        ret += MOD - dp[1][i];
    }
    ret %= MOD;
    ret *= mPow(K + 1, N - K);
    ret %= MOD;
    printf("%lld\n", ret);
    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
// ※※※ 解答不能 ※※※
// yokozuna57氏.
// https://atcoder.jp/contests/cf17-final/submissions/1805242
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MOD = 1e9 + 7;
#define repx(i, a, b) for(LL i = a; i < b; i++)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(LL i = a; i >= b; i--)
LL dp[111][5050];

LL mPow(LL x, LL k){
    if(k == 0) return 1;
    LL ret = mPow(x, k / 2);
    ret *= ret;
    ret %= MOD;
    if(k % 2 == 1){
        ret *= x;
        ret %= MOD;
    }
    return ret;
}

int main(){
    LL N, K;
    scanf("%lld %lld", &N, &K);
    dp[K][0] = K;
    dp[K][1] = 1;
    repr(i, K - 1, 1){
        rep(j, 5050){
            dp[i][j] += dp[i + 1][j] * (K - i);
            dp[i][j + j / i] += dp[i + 1][j] * (i - j % i);
            dp[i][j + j / i + 1] += dp[i + 1][j] * (j % i + 1);
        }
        rep(j, 5050) dp[i][j] %= MOD;
    }
    
    LL ret = mPow(K + 1, K) * N * K;
    ret %= MOD;
    ret *= mPow(2, MOD - 2);
    ret %= MOD;
    repx(i, 1, 5049){
        dp[1][i] *= i;
        dp[1][i] %= MOD;
        ret += MOD - dp[1][i];
    }
    ret %= MOD;
    ret *= mPow(K + 1, N - K);
    ret %= MOD;
    printf("%lld\n", ret);
    return 0;
}
```