#include <bits/stdc++.h>
using namespace std;
long long in() {
  int32_t x;
  scanf("%d", &x);
  return x;
}
inline long long lin() {
  long long x;
  scanf("%lld", &x);
  return x;
}
const long long maxn = 1e6 + 10;
const long long inf = 1e18 + 10;
const long long mod = 1e9 + 7;
inline long long power(long long a, long long b) {
  return b == 0 ? 1 : power(a * a % mod, b >> 1) * (b % 2 ? a : 1) % mod;
}
long long fact[maxn], inv[maxn];
inline long long C(long long n, long long r) {
  if (n < 0 || r < 0 || r > n) return 0;
  return fact[n] * inv[r] % mod * inv[n - r] % mod;
}
long long res;
int32_t main() {
  long long n = in(), m = in();
  fact[0] = inv[0] = 1;
  for (long long i = 1; i < maxn; i++)
    fact[i] = fact[i - 1] * i % mod,
    inv[i] = inv[i - 1] * power(i, mod - 2) % mod;
  for (long long pt = 1; pt <= n; pt++)
    (res += power(m, pt) * power(m - 1, n - pt) % mod * C(n, pt - 1) % mod) %=
        mod;
  (res += power(m, n)) %= mod;
  cout << res << endl;
}

### Prompt

Generate 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>
using namespace std;
long long in() {
  int32_t x;
  scanf("%d", &x);
  return x;
}
inline long long lin() {
  long long x;
  scanf("%lld", &x);
  return x;
}
const long long maxn = 1e6 + 10;
const long long inf = 1e18 + 10;
const long long mod = 1e9 + 7;
inline long long power(long long a, long long b) {
  return b == 0 ? 1 : power(a * a % mod, b >> 1) * (b % 2 ? a : 1) % mod;
}
long long fact[maxn], inv[maxn];
inline long long C(long long n, long long r) {
  if (n < 0 || r < 0 || r > n) return 0;
  return fact[n] * inv[r] % mod * inv[n - r] % mod;
}
long long res;
int32_t main() {
  long long n = in(), m = in();
  fact[0] = inv[0] = 1;
  for (long long i = 1; i < maxn; i++)
    fact[i] = fact[i - 1] * i % mod,
    inv[i] = inv[i - 1] * power(i, mod - 2) % mod;
  for (long long pt = 1; pt <= n; pt++)
    (res += power(m, pt) * power(m - 1, n - pt) % mod * C(n, pt - 1) % mod) %=
        mod;
  (res += power(m, n)) %= mod;
  cout << res << endl;
}

```