思路看这篇博客就行了：https://www.cnblogs.com/zhouzhendong/p/CF1109D.html， 讲的很好
今天学到了prufer编码，这是解决树上计数问题的一大利器，博客：https://www.cnblogs.com/jianglangcaijin/p/5989930.html
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int mod = 1000000007;
const int maxn = 1000010;
LL v[maxn], inv[maxn];
int n, m;
LL qpow(LL a, LL b) {
if(b < 0) return qpow(a, b + mod - 1);
LL ans = 1;
for (; b; b >>= 1) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
}
return ans;
}
void init(int n) {
v[0] = 1;
for (int i = 1; i <= n; i++)
v[i] = (v[i - 1] * i) % mod;
inv[n] = qpow(v[n], mod - 2);
for (int i = n - 1; i >= 0; i--)
inv[i] = (inv[i + 1] * (i + 1)) % mod;
}
LL C(LL a, LL b) {
return ((v[a] * inv[b]) % mod * inv[a - b]) % mod;
}
LL solve(int i) {
LL res = 0;
res = ((C(m - 1, i) * C(n - 2, i)) % mod * qpow(m, n - 2 - i)) % mod;
res = ((res * qpow(n, n - 3 - i)) % mod * (i + 2) ) % mod;
res = (res * v[i]) % mod;
return res;
}
int main() {
int a, b;
scanf("%d%d%d%d", &n, &m, &a, &b);
init(max(n, m) + 1);
LL ans = 0;
for (int i = 0; i < m && i <= n - 2; i++) {
ans = (ans + solve(i)) % mod;
}
cout << ans <<endl;
}