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
#define make_pair mp
#define emplace_back pb
#include <bits/stdc++.h>
using namespace std;
mt19937 mt_rand(time(0));
const int N = 3005;
const long long MOD = 1e9 + 7;
int n;
long long m, dp[N][N][3];
int main() {
	scanf("%d%lld", &n, &m);
    dp[0][0][2] = 1;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) {
        long long cnt = j;

        dp[i][j][0] = (dp[i-1][j][0] + dp[i-1][j][1]) % MOD;
        dp[i][j][0] *= m - cnt;
        dp[i][j][0] %= MOD;

        dp[i][j][1] = dp[i-1][j-1][2] * (m - cnt + 1);
        dp[i][j][1] %= MOD;

        dp[i][j][2] = (dp[i-1][j][0] + dp[i-1][j][1] + dp[i-1][j][2]) % MOD;
        dp[i][j][2] *= cnt;
        dp[i][j][2] %= MOD;
    }
    long long res = 0;
    for(int i=1;i<=n;i++) {
        res += dp[n][i][2];
        res %= MOD;
    }
    printf("%lld\n", res);
	return 0;
}