1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
const int md=1000000007;
int n,m,i,j,k,r;
long long f[3003][3003][2];
void upd(long long& x, long long v) {
  x=(x+v)%md;
}
int main() {
  scanf("%d%d",&n,&m);
  f[1][1][0]=m;
  for (i=1; i<=n; i++) for (j=1; j<=i; j++) for (k=0; k<2; k++) if (f[i][j][k]) {
    if (m>j) upd(f[i+1][j+k][0],f[i][j][k]*(m-j));
    if (j>0) upd(f[i+1][j][1],f[i][j][k]*j);
  }
  for (j=1; j<=n; j++) if (f[n][j][1]) r=(r+f[n][j][1])%md;
  printf("%d\n",r);
  return 0;
}