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
#include <cstdio>
#include <unordered_set>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;

const int M = 1000000007;

int madd(int a, int b) {
  return (LL(a) + b) % M;
}

int mmul(int a, int b) {
  return (LL(a) * b) % M;
}

int main() {
  int n, m; scanf("%d %d", &n, &m);
  
  vector<vector<int>> cuttable, non_cuttable;

  cuttable.push_back({1});
  non_cuttable.push_back({0});

  for (int t = 1; t <= n; ++t) {
    cuttable.push_back({0});
    non_cuttable.push_back({0});

    for (int k = 1; k <= t; ++k) {
      cuttable.back().push_back(
        madd(
          mmul(cuttable[t-1][k], k),
          mmul(non_cuttable[t-1][k], k))
      );
      non_cuttable.back().push_back(
        madd(
          mmul(cuttable[t-1][k-1], max(m-k+1, 0)),
          mmul(non_cuttable[t-1][k], max(m-k, 0)))
      );
    }
/*
    printf("cut of len %d: ", t);
    for (int i : cuttable.back()) printf("%d ", i);
    printf("\n");
    printf("not of len %d: ", t);
    for (int i : non_cuttable.back()) printf("%d ", i);
    printf("\n");
    printf("\n");
*/
  }

  int res = 0;
  for (int i=0; i<=n; ++i) {
    res = madd(res, cuttable[n][i]);
  }
  printf("%d\n", res);

  return 0;
}