Different Subsets For All Tuples (经典，贪心考虑一个子序列是否出现在原序列中)

//https://codeforces.com/problemset/problem/660/E
#include <bits/stdc++.h>
#define ll long long
#define all(a) (a).begin(), (a).end()
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1e6 + 10;

/*
题意：有一个长度为 n 的数列，每个位置上数字的值在 [1, m] 范围内，则共有 m^n 种可能的数列。
分别求出每个数列中本质不同的子序列个数（包含空序列），然后求和

做法：考虑拆贡献，考虑每一个子序列会出现在多少个序列中。
考虑一个子序列是否在一个序列中出现，肯定从左到右一一去匹配这个子序列，所以这个子序列在原序列中出现的位置是最靠左的
也就是说第二个数的位置是这个数的数列中第一个数后面最左的位置

然后去枚举子序列的长度 i 和子序列中最后一个元素出现的位置 j

则 ans = m ^ n + C(j, i) * (m - 1)^(j - i) * m^(n - j + i)

同过化简(会用到二项式定理的定义进行化简)即可都到答案

O(logn) / O(nlogn)
*/

ll mod = 1e9 + 7;
ll fac[N], invfac[N];
ll qpow(ll base, ll pow)
{
    ll ans = 1;
    while (pow)
    {
        if (pow & 1)
            ans = ans * base % mod;
        pow >>= 1;
        base = base * base % mod;
    }
    return ans;
}
inline ll inv(ll x){
    return qpow(x, mod - 2);
}
void init()//不能忘记init和调N的大小
{
     fac[0] = invfac[0] = 1;
     for(int i = 1; i < N; i ++ ) 
         fac[i] = fac[i - 1] * i % mod;
     invfac[N - 1] = qpow(fac[N - 1], mod - 2);
     for(int i = N - 2; i >= 0; i -- ) 
         invfac[i] = invfac[i + 1] * (1 + i) % mod;
}
ll C(int n, int m)
{
    if (n < 0 || m < 0 || m > n) return 0;
    return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}

void solve()
{
    init();

    int n, m;
    cin >> n >> m;

    ll ans = 1;

    // for(int j = 1; j <= n; j++) ans = (ans + qpow(2 * m - 1, j - 1) * inv(qpow(m, j - 1) % mod) % mod) % mod;
    for(int j = 1; j <= n; j++) ans = (ans + qpow((2 * m - 1) * inv(m) % mod, j - 1)) % mod;
    
    ans = ans * qpow(m, n) % mod;

    cout << ans;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}