#include <bits/stdc++.h>
using namespace std;
const int BASE = 1e9 + 7;
const int MAXN = 1e6 + 5;
int n, m;
long long p[MAXN], p0[MAXN], P[MAXN];
long long Pow(long long a, int n) {
  long long ans = 1;
  while (n) {
    if (n & 1) ans = (ans * a) % BASE;
    a = (a * a) % BASE;
    n >>= 1;
  }
  return ans;
}
long long C(long long n, long long i) {
  long long x = P[n];
  x = (x * Pow(P[i], BASE - 2)) % BASE;
  x = (x * Pow(P[n - i], BASE - 2)) % BASE;
  return x;
}
int main() {
  scanf("%d%d", &n, &m);
  p[0] = 1;
  for (int i = 1; i <= n; ++i) p[i] = (p[i - 1] * m) % BASE;
  p0[0] = 1;
  for (int i = 1; i <= n; ++i) p0[i] = (p0[i - 1] * (m - 1)) % BASE;
  P[0] = 1;
  for (int i = 1; i <= n; ++i) P[i] = (P[i - 1] * i) % BASE;
  long long ans = p[n];
  for (int i = 1; i <= n; ++i) {
    long long x = (p[i] * p0[n - i]) % BASE;
    x = (x * C(n, i - 1)) % BASE;
    ans = (ans + x) % BASE;
  }
  cout << ans;
  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 BASE = 1e9 + 7;
const int MAXN = 1e6 + 5;
int n, m;
long long p[MAXN], p0[MAXN], P[MAXN];
long long Pow(long long a, int n) {
  long long ans = 1;
  while (n) {
    if (n & 1) ans = (ans * a) % BASE;
    a = (a * a) % BASE;
    n >>= 1;
  }
  return ans;
}
long long C(long long n, long long i) {
  long long x = P[n];
  x = (x * Pow(P[i], BASE - 2)) % BASE;
  x = (x * Pow(P[n - i], BASE - 2)) % BASE;
  return x;
}
int main() {
  scanf("%d%d", &n, &m);
  p[0] = 1;
  for (int i = 1; i <= n; ++i) p[i] = (p[i - 1] * m) % BASE;
  p0[0] = 1;
  for (int i = 1; i <= n; ++i) p0[i] = (p0[i - 1] * (m - 1)) % BASE;
  P[0] = 1;
  for (int i = 1; i <= n; ++i) P[i] = (P[i - 1] * i) % BASE;
  long long ans = p[n];
  for (int i = 1; i <= n; ++i) {
    long long x = (p[i] * p0[n - i]) % BASE;
    x = (x * C(n, i - 1)) % BASE;
    ans = (ans + x) % BASE;
  }
  cout << ans;
  return 0;
}

```