#include <iostream>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7; // change if needed

struct Modint {
  ll val;
  
  Modint (ll _val = 0)
    : val(_val % MOD) {}

  Modint operator+ (Modint other) const {
    return Modint(val + other.val);
  }

  void operator+= (Modint other) {
    val += other.val;
    val %= MOD;
  }

  Modint operator- () const {
    return Modint(MOD - val);
  }

  Modint operator- (Modint other) const {
    return Modint(val + MOD - other.val);
  }

  void operator-= (Modint other) {
    val += MOD - other.val;
    val %= MOD;
  }

  Modint operator* (Modint other) const {
    return Modint(val * other.val);
  }

  void operator*= (Modint other) {
    val *= other.val;
    val %= MOD;
  }

  bool operator== (Modint other) const {
    return val == other.val;
  }

  bool operator!= (Modint other) const {
    return val != other.val;
  }
};

Modint exp (Modint a, int k) {
  if (k == 0) {
    return Modint(1);
  } else if (k % 2 == 0) {
    Modint half = exp(a, k / 2);
    return half * half;
  } else {
    return a * exp(a, k - 1);
  }
}

Modint inv (Modint a) {
  return exp(a, MOD - 2);
}

ostream& operator<< (ostream& out, Modint p) {
  out << p.val;
  return out;
}

const int MAX_N = 105;
const int MAX_X = 6e3 + 5;

Modint ways [MAX_N][MAX_X];
Modint dp [MAX_N][MAX_X];

int main () {
  int n, K;
  cin >> n >> K;

  ways[n + 1][0] = 1;
  for (int i = n; i >= 1; i--) {
    for (int j = 0; j < MAX_X; j++) {
      for (int k = 0; k <= K; k++) {
        int add_xp, rem;
        if (k > i) {
          add_xp = 0;
          rem = k + j;
        } else {
          int nw = k + j;
          add_xp = nw / i;
          rem = nw % i;
        }

        int nj = j + add_xp;
        if (nj < MAX_X) {
          ways[i][nj] += ways[i + 1][j];
          dp[i][nj] += dp[i + 1][j] + ways[i + 1][j] * Modint(rem);
        }
      }
    }
  }

  Modint ans (0);
  for (int i = 0; i < MAX_X; i++) {
    ans += dp[1][i];
  }
  cout << ans << endl;
}

### Prompt

Please create a solution in cpp 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>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7; // change if needed

struct Modint {
  ll val;
  
  Modint (ll _val = 0)
    : val(_val % MOD) {}

  Modint operator+ (Modint other) const {
    return Modint(val + other.val);
  }

  void operator+= (Modint other) {
    val += other.val;
    val %= MOD;
  }

  Modint operator- () const {
    return Modint(MOD - val);
  }

  Modint operator- (Modint other) const {
    return Modint(val + MOD - other.val);
  }

  void operator-= (Modint other) {
    val += MOD - other.val;
    val %= MOD;
  }

  Modint operator* (Modint other) const {
    return Modint(val * other.val);
  }

  void operator*= (Modint other) {
    val *= other.val;
    val %= MOD;
  }

  bool operator== (Modint other) const {
    return val == other.val;
  }

  bool operator!= (Modint other) const {
    return val != other.val;
  }
};

Modint exp (Modint a, int k) {
  if (k == 0) {
    return Modint(1);
  } else if (k % 2 == 0) {
    Modint half = exp(a, k / 2);
    return half * half;
  } else {
    return a * exp(a, k - 1);
  }
}

Modint inv (Modint a) {
  return exp(a, MOD - 2);
}

ostream& operator<< (ostream& out, Modint p) {
  out << p.val;
  return out;
}

const int MAX_N = 105;
const int MAX_X = 6e3 + 5;

Modint ways [MAX_N][MAX_X];
Modint dp [MAX_N][MAX_X];

int main () {
  int n, K;
  cin >> n >> K;

  ways[n + 1][0] = 1;
  for (int i = n; i >= 1; i--) {
    for (int j = 0; j < MAX_X; j++) {
      for (int k = 0; k <= K; k++) {
        int add_xp, rem;
        if (k > i) {
          add_xp = 0;
          rem = k + j;
        } else {
          int nw = k + j;
          add_xp = nw / i;
          rem = nw % i;
        }

        int nj = j + add_xp;
        if (nj < MAX_X) {
          ways[i][nj] += ways[i + 1][j];
          dp[i][nj] += dp[i + 1][j] + ways[i + 1][j] * Modint(rem);
        }
      }
    }
  }

  Modint ans (0);
  for (int i = 0; i < MAX_X; i++) {
    ans += dp[1][i];
  }
  cout << ans << endl;
}

```