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 <iostream>
using namespace std;
const int MOD = 1000000007;

long long n,m;
long long dp[3000][3000][2];

int main() {
    cin >> n >> m;
    for(int i=0; i<n; i++) {
        dp[i][0][1] = 0;
        dp[i][0][0] = 0;
    }
    dp[0][1][0] = m;
    for(long long i=1; i<n; i++) {
        for(long long k=1; k<n; k++) {
            dp[i][k][0] = (m-k)*dp[i-1][k][0] % MOD;
            dp[i][k][0] += (m-k+1)*dp[i-1][k-1][1];
            dp[i][k][0] %= MOD;
            dp[i][k][1] = k*(dp[i-1][k][0]+dp[i-1][k][1]) % MOD;
            // cout << "dp[" << i << "][" << k << "][P] = " << dp[i][k][1] << endl;
            // cout << "dp[" << i << "][" << k << "][F] = " << dp[i][k][0] << endl;
            // cout << "(" << dp[i][k][1] << ", " << dp[i][k][0] << ") ";
        }
        // cout << endl;
    }
    long long out = 0;
    // for(int i=0; i<n; i++) {
    //     long long sum = 0;
    //     for(int k=0; k<n; k++) {
    //         sum += dp[i][k][0]+dp[i][k][1];
    //     }
    //     cout << m << "^" << i+1 << " = " << sum << endl;
    // }
    for(long long k=1; k<n; k++) {
        out += k*(dp[n-2][k][0]+dp[n-2][k][1]);
        out %= MOD;
    }
    cout << out << endl;
}