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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct mint {
    const static int32_t MODD = 1e9+7;
    int32_t value;
    mint(int32_t v=0) : value(v%MODD) {}
    friend mint operator+(mint a, mint b) {a.value += b.value; if(a.value >= MODD) a.value -= MODD; return a;}
    friend mint operator-(mint a, mint b) {a.value -= b.value; if(a.value < 0) a.value += MODD; return a;}
    friend mint operator*(mint a, mint b) {int64_t res = a.value; res = (res*b.value)%MODD; if(res < 0) res += MODD; return mint(res);}
   
    friend istream& operator>>(istream& in,  mint& a) { return in >> a.value; }
    friend ostream& operator<<(ostream& out, mint a) { return out << a.value; }
    
    mint& operator+=(const mint& b) {return *this = *this+b;}
};


int32_t main(){
    ios::sync_with_stdio(false);
    ll n,k;
    cin >> n >> k;
    ll s = min(n,k);
    vector<mint> dpLocked(s+1);
    vector<mint> dpUnlocked(s+1);
    dpLocked[1] = k;

    vector<mint> dpLocked2(s+1);
    vector<mint> dpUnlocked2(s+1);
    for(int i=2;i<=n;i++) {
        for(int j=1;j<=s;j++) {
            dpLocked2[j] = dpLocked[j]*(k-j);
            dpUnlocked2[j] = dpLocked[j]*j;
            dpLocked2[j] += dpUnlocked[j-1]*(k-j+1);
            dpUnlocked2[j] += dpUnlocked[j]*j;
        }
        swap(dpLocked, dpLocked2);
        swap(dpUnlocked, dpUnlocked2);
    }
    mint res = 0;
    for(int i=0;i<dpLocked.size();i++)
        res += dpUnlocked[i];
    cout<<res<<"\n";
}