#include <bits/stdc++.h>
int faster_in() {
  int r = 0, c;
  for (c = getchar(); c <= 32; c = getchar())
    ;
  if (c == '-') return -faster_in();
  for (; c > 32; r = (r << 1) + (r << 3) + c - '0', c = getchar())
    ;
  return r;
}
using namespace std;
const int INF = int(1e9 + 7);
const int tam = 1e6 + 10;
const int MOD = 1e9 + 7;
long long modPow(long long b, long long e) {
  if (e == 0) return 1;
  long long res = modPow(b, e >> 1);
  res = res * res % MOD;
  if (e & 1) res = res * b % MOD;
  return res % MOD;
}
long long fact[tam], invFact[tam];
long long nCk(long long n, long long k) {
  return (fact[n] * invFact[k] % MOD) * invFact[n - k] % MOD;
}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  fact[0] = invFact[0] = 1;
  for (int i = (int)1; i < (int)tam; ++i) {
    fact[i] = fact[i - 1] * i % MOD;
    invFact[i] = modPow(fact[i], MOD - 2);
  }
  long long n, m;
  cin >> n >> m;
  long long ans = modPow(m, n);
  for (int s = (int)1; s < (int)n + 1; ++s) {
    long long res = modPow(m, s);
    res = res * modPow(m - 1, n - s) % MOD;
    res = res * nCk(n, s - 1) % MOD;
    ans += res;
    if (ans > MOD) ans -= MOD;
  }
  cout << ans << '\n';
  return 0;
}

### Prompt

In CPP, your task is to solve 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>
int faster_in() {
  int r = 0, c;
  for (c = getchar(); c <= 32; c = getchar())
    ;
  if (c == '-') return -faster_in();
  for (; c > 32; r = (r << 1) + (r << 3) + c - '0', c = getchar())
    ;
  return r;
}
using namespace std;
const int INF = int(1e9 + 7);
const int tam = 1e6 + 10;
const int MOD = 1e9 + 7;
long long modPow(long long b, long long e) {
  if (e == 0) return 1;
  long long res = modPow(b, e >> 1);
  res = res * res % MOD;
  if (e & 1) res = res * b % MOD;
  return res % MOD;
}
long long fact[tam], invFact[tam];
long long nCk(long long n, long long k) {
  return (fact[n] * invFact[k] % MOD) * invFact[n - k] % MOD;
}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  fact[0] = invFact[0] = 1;
  for (int i = (int)1; i < (int)tam; ++i) {
    fact[i] = fact[i - 1] * i % MOD;
    invFact[i] = modPow(fact[i], MOD - 2);
  }
  long long n, m;
  cin >> n >> m;
  long long ans = modPow(m, n);
  for (int s = (int)1; s < (int)n + 1; ++s) {
    long long res = modPow(m, s);
    res = res * modPow(m - 1, n - s) % MOD;
    res = res * nCk(n, s - 1) % MOD;
    ans += res;
    if (ans > MOD) ans -= MOD;
  }
  cout << ans << '\n';
  return 0;
}

```