#include <bits/stdc++.h>
using namespace std;
using vint = vector<long long>;
using pint = pair<long long, long long>;
using vpint = vector<pint>;
template <typename A, typename B>
inline void chmin(A& a, B b) {
  if (a > b) a = b;
}
template <typename A, typename B>
inline void chmax(A& a, B b) {
  if (a < b) a = b;
}
template <class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>& p) {
  ost << "{" << p.first << "," << p.second << "}";
  return ost;
}
template <class T>
ostream& operator<<(ostream& ost, const vector<T>& v) {
  ost << "{";
  for (long long i = 0; i < v.size(); i++) {
    if (i) ost << ",";
    ost << v[i];
  }
  ost << "}";
  return ost;
}
inline long long topbit(unsigned long long x) {
  return x ? 63 - __builtin_clzll(x) : -1;
}
inline long long popcount(unsigned long long x) {
  return __builtin_popcountll(x);
}
inline long long parity(unsigned long long x) { return __builtin_parity(x); }
template <uint32_t mod>
struct ModInt {
  uint32_t a;
  ModInt& s(uint32_t vv) {
    a = vv < mod ? vv : vv - mod;
    return *this;
  }
  ModInt(int64_t x = 0) { s(x % mod + mod); }
  ModInt& operator+=(const ModInt& x) { return s(a + x.a); }
  ModInt& operator-=(const ModInt& x) { return s(a + mod - x.a); }
  ModInt& operator*=(const ModInt& x) {
    a = uint64_t(a) * x.a % mod;
    return *this;
  }
  ModInt& operator/=(const ModInt& x) {
    *this *= x.inv();
    return *this;
  }
  ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
  ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
  ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
  ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
  bool operator==(const ModInt& x) const { return a == x.a; }
  bool operator!=(const ModInt& x) const { return a != x.a; }
  bool operator<(const ModInt& x) const { return a < x.a; }
  ModInt operator-() const { return ModInt() - *this; }
  ModInt pow(int64_t n) const {
    ModInt res(1), x(*this);
    while (n) {
      if (n & 1) res *= x;
      x *= x;
      n >>= 1;
    }
    return res;
  }
  ModInt inv() const { return pow(mod - 2); }
};
template <uint32_t mod>
istream& operator>>(istream& in, ModInt<mod>& a) {
  return (in >> a.a);
}
template <uint32_t mod>
ostream& operator<<(ostream& out, const ModInt<mod>& a) {
  return (out << a.a);
}
using mint = ModInt<1000000007>;
template <class Mint, int32_t lg>
struct ModIntTable {
  long long N;
  vector<Mint> facts, finvs, invs;
  ModIntTable() : N(1 << lg), facts(N), finvs(N), invs(N) {
    const uint32_t mod = Mint(-1).a + 1;
    invs[1] = 1;
    for (long long i = 2; i < N; i++) invs[i] = invs[mod % i] * (mod - mod / i);
    facts[0] = 1;
    finvs[0] = 1;
    for (long long i = 1; i < N; i++) {
      facts[i] = facts[i - 1] * i;
      finvs[i] = finvs[i - 1] * invs[i];
    }
  }
  inline Mint fact(long long n) const { return facts[n]; }
  inline Mint finv(long long n) const { return finvs[n]; }
  inline Mint inv(long long n) const { return invs[n]; }
  inline Mint binom(long long n, long long k) const {
    if (n < 0 || k < 0 || k > n) return 0;
    return facts[n] * finvs[k] * finvs[n - k];
  }
  inline Mint perm(long long n, long long k) const {
    if (n < 0 || k < 0 || k > n) return 0;
    return facts[n] * finvs[n - k];
  }
  inline Mint catalan(long long n) {
    return facts[2 * n] * finvs[n + 1] * finvs[n];
  }
};
ModIntTable<mint, 22> mt;
signed main() {
  long long N, M;
  cin >> N >> M;
  mint ans = 0;
  for (long long i = 0; i <= N; i++) {
    mint tmp = mint(2 * M - 1).pow(i);
    tmp *= mint(M).pow(N - i);
    ans += tmp;
  }
  for (long long i = 0; i < N; i++) {
    mint tmp = mint(2 * M - 1).pow(i);
    tmp *= mint(M).pow(N - 1 - i);
    tmp *= M - 1;
    ans -= tmp;
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Your task is to create 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;
using vint = vector<long long>;
using pint = pair<long long, long long>;
using vpint = vector<pint>;
template <typename A, typename B>
inline void chmin(A& a, B b) {
  if (a > b) a = b;
}
template <typename A, typename B>
inline void chmax(A& a, B b) {
  if (a < b) a = b;
}
template <class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>& p) {
  ost << "{" << p.first << "," << p.second << "}";
  return ost;
}
template <class T>
ostream& operator<<(ostream& ost, const vector<T>& v) {
  ost << "{";
  for (long long i = 0; i < v.size(); i++) {
    if (i) ost << ",";
    ost << v[i];
  }
  ost << "}";
  return ost;
}
inline long long topbit(unsigned long long x) {
  return x ? 63 - __builtin_clzll(x) : -1;
}
inline long long popcount(unsigned long long x) {
  return __builtin_popcountll(x);
}
inline long long parity(unsigned long long x) { return __builtin_parity(x); }
template <uint32_t mod>
struct ModInt {
  uint32_t a;
  ModInt& s(uint32_t vv) {
    a = vv < mod ? vv : vv - mod;
    return *this;
  }
  ModInt(int64_t x = 0) { s(x % mod + mod); }
  ModInt& operator+=(const ModInt& x) { return s(a + x.a); }
  ModInt& operator-=(const ModInt& x) { return s(a + mod - x.a); }
  ModInt& operator*=(const ModInt& x) {
    a = uint64_t(a) * x.a % mod;
    return *this;
  }
  ModInt& operator/=(const ModInt& x) {
    *this *= x.inv();
    return *this;
  }
  ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
  ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
  ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
  ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
  bool operator==(const ModInt& x) const { return a == x.a; }
  bool operator!=(const ModInt& x) const { return a != x.a; }
  bool operator<(const ModInt& x) const { return a < x.a; }
  ModInt operator-() const { return ModInt() - *this; }
  ModInt pow(int64_t n) const {
    ModInt res(1), x(*this);
    while (n) {
      if (n & 1) res *= x;
      x *= x;
      n >>= 1;
    }
    return res;
  }
  ModInt inv() const { return pow(mod - 2); }
};
template <uint32_t mod>
istream& operator>>(istream& in, ModInt<mod>& a) {
  return (in >> a.a);
}
template <uint32_t mod>
ostream& operator<<(ostream& out, const ModInt<mod>& a) {
  return (out << a.a);
}
using mint = ModInt<1000000007>;
template <class Mint, int32_t lg>
struct ModIntTable {
  long long N;
  vector<Mint> facts, finvs, invs;
  ModIntTable() : N(1 << lg), facts(N), finvs(N), invs(N) {
    const uint32_t mod = Mint(-1).a + 1;
    invs[1] = 1;
    for (long long i = 2; i < N; i++) invs[i] = invs[mod % i] * (mod - mod / i);
    facts[0] = 1;
    finvs[0] = 1;
    for (long long i = 1; i < N; i++) {
      facts[i] = facts[i - 1] * i;
      finvs[i] = finvs[i - 1] * invs[i];
    }
  }
  inline Mint fact(long long n) const { return facts[n]; }
  inline Mint finv(long long n) const { return finvs[n]; }
  inline Mint inv(long long n) const { return invs[n]; }
  inline Mint binom(long long n, long long k) const {
    if (n < 0 || k < 0 || k > n) return 0;
    return facts[n] * finvs[k] * finvs[n - k];
  }
  inline Mint perm(long long n, long long k) const {
    if (n < 0 || k < 0 || k > n) return 0;
    return facts[n] * finvs[n - k];
  }
  inline Mint catalan(long long n) {
    return facts[2 * n] * finvs[n + 1] * finvs[n];
  }
};
ModIntTable<mint, 22> mt;
signed main() {
  long long N, M;
  cin >> N >> M;
  mint ans = 0;
  for (long long i = 0; i <= N; i++) {
    mint tmp = mint(2 * M - 1).pow(i);
    tmp *= mint(M).pow(N - i);
    ans += tmp;
  }
  for (long long i = 0; i < N; i++) {
    mint tmp = mint(2 * M - 1).pow(i);
    tmp *= mint(M).pow(N - 1 - i);
    tmp *= M - 1;
    ans -= tmp;
  }
  cout << ans << endl;
  return 0;
}

```