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
#include <iostream>
#include <cmath>

using namespace std;

long long dp[3000][3000];

int main() {
    long long modulo = 1000000007;
    long long n,m, ans = 0;
    cin>>n>>m;
    for(int i=0; i<=n-1; ++i) {
        dp[i][0] = 0;
        dp[0][i] = 0;
        dp[1][i] = 0;
    }
    dp[1][1] = m;
    for(int i=2; i<=n-1; ++i)
    for(long long j=1; j<=n-1; ++j) {
        dp[i][j] = dp[i-2][j-1] * (((long long)(max((int)(m-j+1),0)) * (j-1)) % modulo) + dp[i-1][j] * m + dp[i-2][j] * (((j-m) * j) % modulo);
        dp[i][j] = dp[i][j] % modulo;
    }
    for(long long k=1; k<=n-1; ++k) {
        ans += dp[n-1][k] * k;
    }
    ans = ans % modulo;
    if(ans < 0) ans += modulo;
    cout<<ans<<endl;
    
    return 0;
}