1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <vector>
#include <set>
using namespace std;

#define MOD 1000000007
#define FOR(i,a,b) for(int (i)=(int)(a); (i)!=(int)(b); ++(i))

inline int mulmod(int a, int b) {
    return (int)(((long long)(a) * (long long)(b)) % MOD);
}

int powmod(int a, int n) {
    int result = 1, q = a;
    while (n > 0) {
        if (n%2) result = mulmod(result, q);
        q = mulmod(q, q);
        n >>= 1;
    }
    return result;
}

int solve(int n, int m) {
    if (n == 1) return 0;
    if (m == 1) return 1;
    if (m == 2) return mulmod(2, (powmod(2, n-1) - (n-1) + MOD) % MOD);
    if (n == 2) return m;
    if (n == 3) return powmod(m, 2);
    if (n == 4) return (1 + mulmod(m-1, (mulmod(m-1, (3 + m) % MOD) + 4) % MOD)) % MOD ;
    return 0;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    printf("%d\n", solve(n, m));
}