#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
using namespace std;
const long double eps = 1e-7;
const int inf = 1000000010;
const long long INF = 10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 100010, LOG = 20;
long long n, m, k, u, v, x, y, t, a, b, ans;
long long powmod(long long a, long long b) {
  if (!b) return 1;
  if (b & 1) return a * powmod(a * a % mod, b >> 1) % mod;
  return powmod(a * a % mod, b >> 1);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  if (m == 1) return cout << n + 1 << '\n', 0;
  long long A = (2 * m - 1) * powmod(m, mod - 2) % mod;
  long long B = (powmod(A, n) - 1) * powmod(A - 1, mod - 2) % mod;
  cerr << "{"
       << "A"
       << ", "
       << "B"
       << "} = {" << (A) << ", " << (B) << "}" << endl;
  ans = powmod(m, n) * (B + 1) % mod;
  cout << ans << '\n';
  return 0;
}

### Prompt

Develop a solution in CPP 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>
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
using namespace std;
const long double eps = 1e-7;
const int inf = 1000000010;
const long long INF = 10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 100010, LOG = 20;
long long n, m, k, u, v, x, y, t, a, b, ans;
long long powmod(long long a, long long b) {
  if (!b) return 1;
  if (b & 1) return a * powmod(a * a % mod, b >> 1) % mod;
  return powmod(a * a % mod, b >> 1);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  if (m == 1) return cout << n + 1 << '\n', 0;
  long long A = (2 * m - 1) * powmod(m, mod - 2) % mod;
  long long B = (powmod(A, n) - 1) * powmod(A - 1, mod - 2) % mod;
  cerr << "{"
       << "A"
       << ", "
       << "B"
       << "} = {" << (A) << ", " << (B) << "}" << endl;
  ans = powmod(m, n) * (B + 1) % mod;
  cout << ans << '\n';
  return 0;
}

```