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
// DP[false][k] ->(m-k) DP[false][k]
// DP[true][k] ->(m-k) DP[false][k+1]
// DP[false][k] ->k DP[true][k]
// DP[true][k] ->k DP[true][k]

#include <iostream>
using namespace std;
typedef long long ll;

const int P = 1e9 + 7;

int DP[2][3010];

int main() {
    ios::sync_with_stdio(false); cin.tie();
    ll n, m;
    cin >> n >> m;

    DP[true][0] = 1;

    for (int i = 0; i < n; i++) {
        for (ll k = i; k >= 0; k--) {
            int f = DP[false][k], t = DP[true][k];
            DP[true][k] = k * (f + t) % P;
            DP[false][k] = (m-k) * f % P;
            DP[false][k+1] = ((m-k) * t + DP[false][k+1]) % P;
        }
    }

    ll sum = 0;
    for (int k = 0; k <= n; k++) {
        sum += DP[true][k];
    }
    sum %= P;
    cout << sum << '\n';
}