//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
// 293206GT
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <unordered_set>
#include <stack>
#include <string>
#include<algorithm>
#include <random>
#include <bitset>
#include <chrono>

typedef long long ll;
#define int ll
using namespace std;
#define put(a) cout << (a) << '\n'
#define sqr(x) (x) * (x)
typedef pair<int, int> pii;
typedef long double ld;
typedef pair<int, int> pld;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<pii> vpii;
#define rep(x, y, a) for (int x = (y); x < (int)(a); ++x)
#define all(a) a.begin(), a.end()
#define chkmax(a, b) a = max(a, (b))
#define chkmin(a, b) a = min(a, (b))

namespace IO {

    template<class A, class B>
    ostream &operator<<(ostream &out, vector<pair<A, B>> a);

    template<class A>
    ostream &operator<<(ostream &out, vector<A> a);

    template<class A, class B>
    ostream &operator<<(ostream &out, pair<A, B> a) {
        out << a.first << " " << a.second;
        return out;
    }

    template<class A, class B>
    ostream &operator<<(ostream &out, vector<pair<A, B>> a) {
        for (pair<A, B> x: a)
            out << x.first << " " << x.second << '\n';
        return out;
    }

    template<class A>
    ostream &operator<<(ostream &out, vector<A> a) {
        for (A x: a) out << x << ' ';
        return out;
    }

    template<class A, class B>
    istream &operator>>(istream &in, pair<A, B> &a) {
        in >> a.first >> a.second;
        return in;
    }

    template<class A>
    istream &operator>>(istream &in, vector<A> &a) {
        for (A &x: a) in >> x;
        return in;
    }
}
using namespace IO;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int M = 1e9 + 7;
int bp(int a, int b) {
    if (b == 0) return 1;
    int x = bp(a, b/2);
    x = (x*x) %M;
    if (b % 2) x = x * a % M;
    return x;
}
void solve() {
    int n, k;
    cin >> n >> k;
    vector<vi> dp(n + 1, vi(4e3, 0));
    rep(i, 1, n + 1) rep(j, 0, dp[i].size()) {
        rep(m, 0, k + 1) {
            int incr = (m > i?0:(m + j)/i);
            if (j + incr < dp[i].size()) {
                dp[i][j] += dp[i - 1][j + incr] + (m > i?m + j:(m + j) % i) * bp(k + 1, i - 1);
                dp[i][j] %= M;
            }
        }
    }
    put(dp[n][0]);
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(30);
    int q = 1;
//    cin >> q;
//    freopen("input.txt", "r", stdin);
    while (q--) solve();
}

### 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
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
// 293206GT
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <unordered_set>
#include <stack>
#include <string>
#include<algorithm>
#include <random>
#include <bitset>
#include <chrono>

typedef long long ll;
#define int ll
using namespace std;
#define put(a) cout << (a) << '\n'
#define sqr(x) (x) * (x)
typedef pair<int, int> pii;
typedef long double ld;
typedef pair<int, int> pld;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<pii> vpii;
#define rep(x, y, a) for (int x = (y); x < (int)(a); ++x)
#define all(a) a.begin(), a.end()
#define chkmax(a, b) a = max(a, (b))
#define chkmin(a, b) a = min(a, (b))

namespace IO {

    template<class A, class B>
    ostream &operator<<(ostream &out, vector<pair<A, B>> a);

    template<class A>
    ostream &operator<<(ostream &out, vector<A> a);

    template<class A, class B>
    ostream &operator<<(ostream &out, pair<A, B> a) {
        out << a.first << " " << a.second;
        return out;
    }

    template<class A, class B>
    ostream &operator<<(ostream &out, vector<pair<A, B>> a) {
        for (pair<A, B> x: a)
            out << x.first << " " << x.second << '\n';
        return out;
    }

    template<class A>
    ostream &operator<<(ostream &out, vector<A> a) {
        for (A x: a) out << x << ' ';
        return out;
    }

    template<class A, class B>
    istream &operator>>(istream &in, pair<A, B> &a) {
        in >> a.first >> a.second;
        return in;
    }

    template<class A>
    istream &operator>>(istream &in, vector<A> &a) {
        for (A &x: a) in >> x;
        return in;
    }
}
using namespace IO;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int M = 1e9 + 7;
int bp(int a, int b) {
    if (b == 0) return 1;
    int x = bp(a, b/2);
    x = (x*x) %M;
    if (b % 2) x = x * a % M;
    return x;
}
void solve() {
    int n, k;
    cin >> n >> k;
    vector<vi> dp(n + 1, vi(4e3, 0));
    rep(i, 1, n + 1) rep(j, 0, dp[i].size()) {
        rep(m, 0, k + 1) {
            int incr = (m > i?0:(m + j)/i);
            if (j + incr < dp[i].size()) {
                dp[i][j] += dp[i - 1][j + incr] + (m > i?m + j:(m + j) % i) * bp(k + 1, i - 1);
                dp[i][j] %= M;
            }
        }
    }
    put(dp[n][0]);
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(30);
    int q = 1;
//    cin >> q;
//    freopen("input.txt", "r", stdin);
    while (q--) solve();
}

```