#include <bits/stdc++.h>
using namespace std;
const int kMod = 1e9 + 7;
struct ModInt {
  long long n;
  ModInt(long long n = 0) : n(n % kMod) {}
  ModInt operator+(const ModInt& oth) { return n + oth.n; }
  ModInt operator-(const ModInt& oth) { return n - oth.n; }
  ModInt operator*(const ModInt& oth) { return n * oth.n; }
  long long get() { return n < 0 ? n + kMod : n; }
};
ModInt lgpow(ModInt b, int e) {
  ModInt r;
  for (r = 1; e; e /= 2, b = b * b)
    if (e % 2) r = r * b;
  return r;
}
ModInt inv(ModInt x) { return lgpow(x, kMod - 2); }
int main() {
  int n, m;
  cin >> n >> m;
  vector<ModInt> fact(n + 1, 1);
  for (int i = 1; i <= n; ++i) {
    fact[i] = fact[i - 1] * i;
  }
  vector<ModInt> invfact(n + 1, 1);
  invfact[n] = inv(fact[n]);
  for (int i = n - 1; i >= 1; --i) {
    invfact[i] = invfact[i + 1] * (i + 1);
  }
  auto choose = [&](int n, int k) {
    return fact[n] * invfact[k] * invfact[n - k];
  };
  ModInt invm = inv(m);
  ModInt mm = invm * (m - 1);
  ModInt pw = 1;
  ModInt ans = 1;
  for (int d = 0; d < n; ++d) {
    ModInt res = choose(n, n - d - 1);
    res = res * pw;
    pw = pw * mm;
    ans = ans + res;
  }
  for (int i = 0; i < n; ++i) ans = ans * m;
  cout << ans.get() << endl;
  return 0;
}

### Prompt

Create a solution in cpp for 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;
const int kMod = 1e9 + 7;
struct ModInt {
  long long n;
  ModInt(long long n = 0) : n(n % kMod) {}
  ModInt operator+(const ModInt& oth) { return n + oth.n; }
  ModInt operator-(const ModInt& oth) { return n - oth.n; }
  ModInt operator*(const ModInt& oth) { return n * oth.n; }
  long long get() { return n < 0 ? n + kMod : n; }
};
ModInt lgpow(ModInt b, int e) {
  ModInt r;
  for (r = 1; e; e /= 2, b = b * b)
    if (e % 2) r = r * b;
  return r;
}
ModInt inv(ModInt x) { return lgpow(x, kMod - 2); }
int main() {
  int n, m;
  cin >> n >> m;
  vector<ModInt> fact(n + 1, 1);
  for (int i = 1; i <= n; ++i) {
    fact[i] = fact[i - 1] * i;
  }
  vector<ModInt> invfact(n + 1, 1);
  invfact[n] = inv(fact[n]);
  for (int i = n - 1; i >= 1; --i) {
    invfact[i] = invfact[i + 1] * (i + 1);
  }
  auto choose = [&](int n, int k) {
    return fact[n] * invfact[k] * invfact[n - k];
  };
  ModInt invm = inv(m);
  ModInt mm = invm * (m - 1);
  ModInt pw = 1;
  ModInt ans = 1;
  for (int d = 0; d < n; ++d) {
    ModInt res = choose(n, n - d - 1);
    res = res * pw;
    pw = pw * mm;
    ans = ans + res;
  }
  for (int i = 0; i < n; ++i) ans = ans * m;
  cout << ans.get() << endl;
  return 0;
}

```