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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <unordered_set>
#include <queue>

using namespace std;
long long int MOD = 1000000007LL;

long long int cokolwiek(long long int size, long long int m){
	long long int i = size;
	long long int tmp=1;
	while(i--){
		tmp *= m;
		tmp %= MOD;
	}
	return tmp;
}

long long int policz(long long int n, long long int m) {
	if(n == 1){
		return 0;
	}
	if(m == 1){
		return 1;
	}
	if(n == 2){
		return m;
	}
	if(n == 3){
		long long int tmp = m * m;
		return tmp%MOD;
	}
	long long int part_1 = (cokolwiek(n-2,m)%MOD) * m;
	
	//cout << part_1 << "\n";
	
	long long int part_2 = 0;
	
	for(int i = 1; i < n-1; ++i){
			long long int tmp2 = 1;
			tmp2 *= (cokolwiek(i-1,m) % MOD) * m;
			//cout << "--------------------------" << "\n";
			//cout << (cokolwiek(i-1,m) % MOD) * m << "\n";
			tmp2 %= MOD;
			//cout << (policz(n-1-i,m-1) % MOD) << "\n";
			//cout << "--------------------------" << "\n";
			tmp2 *= (policz(n-1-i,m-1) % MOD);
			tmp2 %= MOD;
			part_2 += tmp2%MOD;
	}
	
	//cout << part_2 << "\n";
	
	return (part_1 % MOD + part_2 % MOD) % MOD;
}

int main(){
	long long int n = 0;
	long long int m = 0;

	cin >> n;
	cin >> m;
	
	long long int wynik = 0;
	
	wynik = policz(n, m);
	
	cout << wynik << "\n";
	
	
	
	return 0;
}