#include <bits/stdc++.h>
using namespace std;
pair<int, int> eea(int a, int b) {
  if (b == 0) return make_pair(1, 0);
  auto ret = eea(b, a % b);
  return make_pair(ret.second, ret.first - a / b * ret.second);
}
struct Modint {
  int val;
  Modint(int nval = 0) { val = nval; }
  Modint& operator+=(Modint r) {
    val = (val + r.val) % 1000000007;
    return *this;
  }
  Modint& operator-=(Modint r) {
    val = (val + 1000000007 - r.val) % 1000000007;
    return *this;
  }
  Modint& operator*=(Modint r) {
    val = 1LL * val * r.val % 1000000007;
    return *this;
  }
  Modint operator+(Modint r) { return Modint(*this) += r; }
  Modint operator-(Modint r) { return Modint(*this) -= r; }
  Modint operator*(Modint r) { return Modint(*this) *= r; }
  Modint inverse() {
    int ret = eea(val, 1000000007).first;
    while (ret < 0) ret += 1000000007;
    return ret;
  }
};
int main() {
  int n, m;
  cin >> n >> m;
  if (m == 1) {
    cout << n + 1 << '\n';
    return 0;
  }
  vector<Modint> lv(n + 1);
  lv[0] = 1;
  lv[1] = 1;
  Modint first = Modint(m - 1) * Modint(m).inverse();
  Modint mpow = Modint(m);
  Modint fpow = first;
  for (int i = 1; i < n; i++) mpow *= m;
  for (int i = 1; i < n; i++) {
    lv[i + 1] = fpow + (lv[i] * first - fpow) + (lv[i] - 1) + 1;
    fpow *= first;
  }
  Modint result = 0;
  for (int i = 0; i <= n; i++) {
    lv[i] *= mpow;
    result += lv[i];
  }
  cout << result.val << '\n';
  return 0;
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

For a sequence a of n integers between 1 and m, inclusive, denote f(a) as the number of distinct subsequences of a (including the empty subsequence).

You are given two positive integers n and m. Let S be the set of all sequences of length n consisting of numbers from 1 to m. Compute the sum f(a) over all a in S modulo 109 + 7.

Input

The only line contains two integers n and m (1 ≤ n, m ≤ 106) — the number of elements in arrays and the upper bound for elements.

Output

Print the only integer c — the desired sum modulo 109 + 7.

Examples

Input

1 3


Output

6


Input

2 2


Output

14


Input

3 3


Output

174

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
pair<int, int> eea(int a, int b) {
  if (b == 0) return make_pair(1, 0);
  auto ret = eea(b, a % b);
  return make_pair(ret.second, ret.first - a / b * ret.second);
}
struct Modint {
  int val;
  Modint(int nval = 0) { val = nval; }
  Modint& operator+=(Modint r) {
    val = (val + r.val) % 1000000007;
    return *this;
  }
  Modint& operator-=(Modint r) {
    val = (val + 1000000007 - r.val) % 1000000007;
    return *this;
  }
  Modint& operator*=(Modint r) {
    val = 1LL * val * r.val % 1000000007;
    return *this;
  }
  Modint operator+(Modint r) { return Modint(*this) += r; }
  Modint operator-(Modint r) { return Modint(*this) -= r; }
  Modint operator*(Modint r) { return Modint(*this) *= r; }
  Modint inverse() {
    int ret = eea(val, 1000000007).first;
    while (ret < 0) ret += 1000000007;
    return ret;
  }
};
int main() {
  int n, m;
  cin >> n >> m;
  if (m == 1) {
    cout << n + 1 << '\n';
    return 0;
  }
  vector<Modint> lv(n + 1);
  lv[0] = 1;
  lv[1] = 1;
  Modint first = Modint(m - 1) * Modint(m).inverse();
  Modint mpow = Modint(m);
  Modint fpow = first;
  for (int i = 1; i < n; i++) mpow *= m;
  for (int i = 1; i < n; i++) {
    lv[i + 1] = fpow + (lv[i] * first - fpow) + (lv[i] - 1) + 1;
    fpow *= first;
  }
  Modint result = 0;
  for (int i = 0; i <= n; i++) {
    lv[i] *= mpow;
    result += lv[i];
  }
  cout << result.val << '\n';
  return 0;
}

```