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
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007;
long long wynik;
long long w;
long long n, m;

long long pot(long long a, long long b){
	if(b == 0) return 1;
	if(b&1) return a%MOD*pot(a, b-1)%MOD;
	w = pot(a, b>>1)%MOD;
	return (w*w)%MOD;
}

long long Oblicz(long long a, long long b, long long c){
	if(b == 0 || b == 1) return 1;
	return (pot(m, b-2)%MOD*(a-1)*Oblicz(a, c-b-2, c-b)%MOD)%MOD;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	wynik = pot(m, n-2)%MOD;
	for(int i = n-2; i >= 2; i--){
		wynik = (wynik+Oblicz(m, i, n)%MOD)%MOD;
	}
	cout << (wynik*m)%MOD;
	return 0;
}