#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
void add(int &a, int x) {
  a += x;
  if (a > mod) a -= mod;
}
int mul(int a, int b) { return (long long)a * b % mod; }
int modpow(int a, int n) {
  int res = 1;
  for (; n > 0; n >>= 1) {
    if (n & 1) res = mul(res, a);
    a = mul(a, a);
  }
  return res;
}
int inv(int x) { return modpow(x, mod - 2); }
const int N = 1000101;
int fact[N];
int invfact[N];
int C(int n, int k) { return mul(fact[n], mul(invfact[n - k], invfact[k])); }
int n, m;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  fact[0] = invfact[0] = 1;
  for (int i = 1; i < N; i++) {
    fact[i] = mul(i, fact[i - 1]);
    invfact[i] = mul(invfact[i - 1], inv(i));
  }
  cin >> n >> m;
  int res = 0;
  for (int x = 1; x <= n; x++) {
    int sumint = C(n, x - 1);
    add(res, mul(modpow(m - 1, n - x), mul(modpow(m, x), sumint)));
  }
  add(res, modpow(m, n));
  cout << res << endl;
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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 mod = 1e9 + 7;
void add(int &a, int x) {
  a += x;
  if (a > mod) a -= mod;
}
int mul(int a, int b) { return (long long)a * b % mod; }
int modpow(int a, int n) {
  int res = 1;
  for (; n > 0; n >>= 1) {
    if (n & 1) res = mul(res, a);
    a = mul(a, a);
  }
  return res;
}
int inv(int x) { return modpow(x, mod - 2); }
const int N = 1000101;
int fact[N];
int invfact[N];
int C(int n, int k) { return mul(fact[n], mul(invfact[n - k], invfact[k])); }
int n, m;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  fact[0] = invfact[0] = 1;
  for (int i = 1; i < N; i++) {
    fact[i] = mul(i, fact[i - 1]);
    invfact[i] = mul(invfact[i - 1], inv(i));
  }
  cin >> n >> m;
  int res = 0;
  for (int x = 1; x <= n; x++) {
    int sumint = C(n, x - 1);
    add(res, mul(modpow(m - 1, n - x), mul(modpow(m, x), sumint)));
  }
  add(res, modpow(m, n));
  cout << res << endl;
  return 0;
}

```