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
#include<cstdio>
#include<algorithm>
#define S 3007

using namespace std;
typedef long long ll;

ll dp[S][S];
ll dp2[S][S];

ll mod = 1000000007;

int main(void){
    int n;
    ll m;
    scanf("%d %lld",&n,&m);
    dp[1][1] = 0;
    dp[2][1] = m;
    dp2[2][1] = (ll)m * (ll)(m-1);
    dp2[2][1] %= mod;
    for(int i = 2; i <= n;i++){
        for(int j = 1; j <= n;j++){
            dp[i][j] %= mod;
            dp2[i][j] %= mod;
            dp2[i+1][j+1] += dp[i][j] * (ll)(m-j);
            dp[i+1][j] += dp[i][j] * (ll)j;
            dp2[i+1][j] += dp2[i][j] * (ll)(m-j);
            dp[i+1][j] += dp2[i][j] * (ll)j;
        }
    }
    ll ans = 0;
    for(int i = 1; i <= n;i++){
        ans += dp[n][i];
    }
    ans %= mod;
    printf("%lld",ans);

    return 0;
}