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
#include <iostream>
long long n,m;
long long dyn[3001][3001][2];//len,ends
long long mod=1000000007;
long long result;
int main(){
    std::cin>>n>>m;
    dyn[0][0][1]=1;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=std::min(m,n);j++){
        dyn[i][j][0]=dyn[i-1][j][0]*(m-j);
        dyn[i][j][1]=(dyn[i-1][j][0]+dyn[i-1][j][1])*(j);
        dyn[i][j][0]+=dyn[i-1][j-1][1]*(m-j+1);
        dyn[i][j][0]%=mod;
        dyn[i][j][1]%=mod;
        //std::cout<<dyn[i-1][j-1][1]<<" "<<(m-j+1)<<std::endl;;
        //std::cout<<i<<" "<<j<<" "<<dyn[i][j][0]<<" "<<dyn[i][j][1]<<std::endl;
    }
    for(int i=0;i<=std::min(m,n);i++){
        //std::cout<<dyn[n][i][1]<<std::endl;
        result=(result+dyn[n][i][1])%mod;
    }
    std::cout<<result<<std::endl;

}