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
#include <stdio.h>

const int MOD = 1000000007;

int I[3001][1501][2];

int main()
{
  int n, m;
  
  scanf("%d%d", &n, &m);
  
  I[0][0][1] = 1;
  
  for (int i = 1; i <= n; i++)
      for (int s = 1; s <= (i+1)/2; s++)
      {
          I[i][s][1] = ((long long)s * (I[i-1][s][0] + I[i-1][s][1])) % MOD;
          I[i][s][0] = ((long long)(m - s)     * I[i-1][s][0] +
                        (long long)(m - s + 1) * I[i-1][s-1][1]) % MOD;
      }

  int answer = 0;
  for (int s = 0; s <= (n+1)/2; s++)
      answer = (answer + I[n][s][1]) % MOD;
  
  printf("%d\n", answer);
  
  return 0;
}