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

using namespace std;

const int MOD = 1e9+7;

int maxn, m, w[3001][3001][2];

int f(int n, int ilek, int z) {
    if (w[n][ilek][z]) return w[n][ilek][z];
    long long wynik = 0;
    if (n == 0) {
        if (z == 0) wynik = 1;
        goto end;
    }
    if (n == 1) {
        wynik = ilek;
        goto end;
    }
    
    if (z) wynik += f(n - 1, ilek, 0);
    if (ilek > z) wynik += (long long) f(n-1, ilek, 0) * (ilek - z) % MOD;
    if (ilek < m) {
        if (z) wynik += (long long) f(n - 1, ilek, 1) * (m - ilek) % MOD;
        else wynik += (long long) f(n - 1, ilek + 1, 1) * (m - ilek) % MOD;
    }
    
    end:
    wynik %= MOD;
    w[n][ilek][z] = wynik;
    return wynik;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> maxn >> m;
    
    cout << f(maxn, 0, 0) << endl;
}