Different Subsets For All Tuples
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.
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.
Print the only integer c — the desired sum modulo 109 + 7.
import sys
from math import factorial
input = sys.stdin.readline

def C(n, m):
    return factorial(n) // factorial(m) // factorial(n - m)

def solve():
    (n, m) = map(int, input().split())
    if m == 1:
        print(n + 1)
        return
    MOD = int(1000000000.0 + 7)
    r = (pow(2 * m - 1, n, MOD) - pow(m, n, MOD)) * m * pow(m - 1, MOD - 2, MOD)
    r += pow(m, n, MOD)
    print(r % MOD)
solve()
p = 10 ** 9 + 7
(n, m) = map(int, input().split())
print(n + 1 if m == 1 else pow(m, n, p) * (1 + (pow(2 * m - 1, n, p) * pow(m, p - 1 - n, p) - 1) * m * pow(m - 1, p - 2, p)) % p)
P = 10 ** 9 + 7
(n, k) = map(int, input().split())
print(n + 1 if k == 1 else (k * pow(2 * k - 1, n, P) - pow(k, n, P)) * pow(k - 1, P - 2, P) % P)