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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <cstdio>

#define MOD 1000000007  
//           123456789

#define MAXN 3200

// Z[N][K] is the number ways to choose N numbers in 1..M, such that the total
//   sequence cannot be cut, given that the last cut tree was unmatched, and could
//   have been (depending on choices made) any of the K first types. Equivalently
//   it's the number of ways to finish the sequence 1122334455..(K-1)(K-1)K (note
//   the last K is not doubled).
// We consider N >= 0, K >= 1.

// Z[N][K] satisfies the following recurrential equation:
// Z[0][K] = 1 (for K > 0) - since the last tree was unmatched, the empty sequence
//   is a valid way to finish with a sequence that cannot be cut.
// Z[N][K] = (M-K) Z(N-1, K) + sum(i=1..N-1) K**i (M-K) Z(N-i-1, K+1)
//   The explanation for the equation. If we choose as the next number one of the
//   m-K numbers larger than K, then we just extended the sequence. This tree cannot
//   be cut (since we didn't close the last sequence), and we need to construct a
//   sequence one-shorter, with the same prefix behavior.
//   The alternative is to choose some sequence of numbers from (1..K), followed by
//   a number from outside the set (we sum over the length of the sequence from (1..K).
//   In that case, the extra number we chose could also be the beginning of the next cut
//   (and we can also continue the existing cuts). We know that a cut is open (the new
//   number cannot close a cut), so we get the second factor.
//   Reorganizing a bit, this gives
// Z[N][K] = (M - K) (Z(N-1, K) + sum(i=1..N-1) K**i Z(N-i-1, K+1) 
long long int Z[MAXN][MAXN];

// The naive calculation of the recursion above is cubic, so we need to do better.
// Let S[N][K] = sum(i=1..N-1) K**i Z(N-i-1, K+1). Let's transform this a bit:
//             = K * sum(i=1..N-1) K ** (i-1) Z(N-1 - i, K+1).
// Transform, j = i-1, i = j+1.
//             = K * sum(j=0..N-2) K ** j Z(N-1 - j - 1, K+1) =
//             = K * Z(N - 2, K + 1) + K * sum(j=1..(N-1)-1) K**j Z((N-1) - j - 1, K+1)
//             = K * Z(N-2, K+1) + K * S(N-1, K).
// Which can be calculated in constant time. 
long long int S[MAXN][MAXN];

// So, the final recursions:
// Z[N][K] = (M-K) (Z[N-1][K] + S[N][K])
// S[N][K] = K (Z[N-2][K+1] + S[N-1][K])
// The initialization is Z[0][K] = 1 for any K
//                       Z[N][M] = 0 for any N 
// And for S, S[0][K] = S[1][K] = 0 (the respective sums are empty).

// And the final result will be M**N - M Z[N-1][1]

int NN, M;
int main() {
  scanf("%d %d", &NN, &M);  
  for (int k = 0; k < MAXN; ++k) {
    Z[0][k] = 1;
    S[0][k] = 0;
    S[1][k] = 0;
    Z[1][k] = (M - k);
  } 
  for (int N = 2; N < NN; ++N) {
    for (int K = 1; K < MAXN; ++K) {
      S[N][K] = (((long long) K) * (Z[N-2][K+1] + S[N-1][K])) % MOD;  
      Z[N][K] = (((long long) (M - K)) * (Z[N-1][K] + S[N][K])) % MOD;
    }
  }
  long long int res = 1;
  for (int i = 0; i < NN; ++i) {
    res = (res * M) % MOD;
  }
  res += MOD;
  res -= (M * Z[NN-1][1]) % MOD;
  res %= MOD;
  printf("%d\n", (int) res);
  return 0;
}