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
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>

using namespace std;

const int N = 3'007;
const int MOD = 1'000'000'007;

int n, m;
int dp[N][N][3];

void add(int &a, int b) {
    a += b;
    if (a >= MOD) {
        a -= MOD;
    }
}

int main() 
{
    scanf("%d %d", &n, &m);

    dp[1][1][1] = m;
    for (int len = 1; len < n; ++len) {
        for (int bad = 0; bad <= len && bad <= m; ++bad) {
            { /* this is an arbitrary good element */
                add(dp[len + 1][bad][0], 1LL * dp[len][bad][0] * (m - bad) % MOD);
                add(dp[len + 1][bad][2], 1LL * dp[len][bad][0] * bad % MOD);
            }

            { /* this is the first occurence of bad element */
                add(dp[len + 1][bad][0], 1LL * dp[len][bad][1] * (m - bad) % MOD);
                add(dp[len + 1][bad][2], 1LL * dp[len][bad][1] * bad % MOD);
            }

            { /* this is the second occurence of bad element */
                add(dp[len + 1][bad + 1][1], 1LL * dp[len][bad][2] * (m - bad) % MOD);
                add(dp[len + 1][bad][2], 1LL * dp[len][bad][2] * bad % MOD);
            }
        }
    }

    int ans = 0;
    for (int bad = 0; bad <= n && bad <= m; ++bad) {
        add(ans, dp[n][bad][2]);
    }

    printf("%d\n", ans);
    return 0;
}