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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll MOD=1e9+7, LIM=3e3+7;
ll dp[LIM][LIM], T[LIM][LIM], n, m;
ll pot(ll a, ll b) {
	return T[m-a][b];
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	rep(i, LIM) {
		if(m-i!=0) T[i][0]=1;
		for(ll j=1; j<LIM; ++j) T[i][j]=(T[i][j-1]*(m-i))%MOD;
	}
	for(ll j=min(n, m)-1; j>=0; --j) {
		dp[1][j]=m-j;
		ll x=0;
		for(ll i=2; i<=n; ++i) {
			if(i>=3) {
				x=(x*(m-j-1))%MOD;
				x=(x+dp[i-2][j+1])%MOD;
			}
			dp[i][j]=(x*(j+1))%MOD;
			ll p=(j*dp[i-1][j])%MOD;
			dp[i][j]=(dp[i][j]+pot(m-j-1, i-1))%MOD;
			dp[i][j]=(dp[i][j]*(m-j))%MOD;
			dp[i][j]=(dp[i][j]+p)%MOD;
		}
	}
	ll ans=pot(m, n);
	ans=(ans-dp[n][0]+MOD)%MOD;
	cout << ans << '\n';
}