#include <bits/stdc++.h>
const int ntf = 1e9 + 7;
inline char rc() {
  static char buf[1048576], *pn = buf, *pe = buf;
  return (pn == pe) &&
                 (pe = (pn = buf) + fread(buf, 1, 1048576, stdin), pn == pe)
             ? EOF
             : *pn++;
}
inline long long _read() {
  long long x = 0;
  char cc = rc();
  while (cc < '0' || cc > '9') cc = rc();
  while (cc >= '0' && cc <= '9') x = x * 10 + cc - '0', cc = rc();
  return x;
}
long long n, m, k, ans;
long long pw1[1000003], pw2[1000003];
int main() {
  n = _read(), m = _read();
  k = m * 2 - 1;
  pw1[0] = pw2[0] = 1;
  for (int i = 0; i < n; ++i)
    pw1[i + 1] = pw1[i] * m % ntf, pw2[i + 1] = pw2[i] * k % ntf;
  for (int i = 0; i < n; ++i) ans += pw1[n - i] * pw2[i] % ntf;
  printf("%I64d\n", (ans + pw1[n]) % ntf);
  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>
const int ntf = 1e9 + 7;
inline char rc() {
  static char buf[1048576], *pn = buf, *pe = buf;
  return (pn == pe) &&
                 (pe = (pn = buf) + fread(buf, 1, 1048576, stdin), pn == pe)
             ? EOF
             : *pn++;
}
inline long long _read() {
  long long x = 0;
  char cc = rc();
  while (cc < '0' || cc > '9') cc = rc();
  while (cc >= '0' && cc <= '9') x = x * 10 + cc - '0', cc = rc();
  return x;
}
long long n, m, k, ans;
long long pw1[1000003], pw2[1000003];
int main() {
  n = _read(), m = _read();
  k = m * 2 - 1;
  pw1[0] = pw2[0] = 1;
  for (int i = 0; i < n; ++i)
    pw1[i + 1] = pw1[i] * m % ntf, pw2[i + 1] = pw2[i] * k % ntf;
  for (int i = 0; i < n; ++i) ans += pw1[n - i] * pw2[i] % ntf;
  printf("%I64d\n", (ans + pw1[n]) % ntf);
  return 0;
}

```