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
#include <bits/stdc++.h>
#define REP(i,n) for (int _n=(n), i=0;i<_n;++i)
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for (int i=(a),_b=(b);i>=_b;--i)
#define TRACE(x) std::cerr << "TRACE(" #x ")" << std::endl;
#define DEBUG(x) std::cerr << #x << " = " << (x) << std::endl;

void init_io() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

template<unsigned MOD>
class Modulo {
  unsigned v;
public:
  explicit Modulo(unsigned x=0):v(x) {}
  unsigned get() const { return v; }
  Modulo operator+(Modulo b) const {
    unsigned res = v+b.v;
    if (res >= MOD) res -= MOD;
    return Modulo(res);
  }
  Modulo operator-(Modulo b) const { return *this + Modulo(MOD-b.v); }
  Modulo operator*(Modulo b) const { return Modulo(std::uint64_t(v) * b.v % MOD); }
  Modulo add_mul(Modulo b, Modulo c) const { return Modulo((v + std::uint64_t(b.v) * c.v) % MOD); }
};
using Mod = Modulo<1'000'000'007>;

Mod calc(const int n0, Mod m) {
  // index = possible in progress cuts
  std::vector<Mod> start_ok(n0+1, Mod(1));
  std::vector<Mod> start_not_ok(n0+1, Mod(0));
  std::vector<Mod> next_start_ok = start_ok;
  std::vector<Mod> next_start_not_ok = start_not_ok;

  FORD(n, n0 - 1, 0) {
    FOR(in_progress, 0, n) {
      const Mod num_in_progress = Mod(in_progress);
      const Mod continue_or_stop = num_in_progress * start_ok[in_progress];
      const Mod num_other = m - num_in_progress;

      next_start_ok[in_progress] =
        continue_or_stop.add_mul(num_other, start_not_ok[in_progress + 1]);

      next_start_not_ok[in_progress] =
        continue_or_stop.add_mul(num_other, start_not_ok[in_progress]);
    }

    start_ok.swap(next_start_ok);
    start_not_ok.swap(next_start_not_ok);
  }

  return start_ok[0];
}

int main() {
  init_io();

  int n;
  unsigned m_raw;
  std::cin >> n >> m_raw;
  const auto res = calc(n, Mod(m_raw));
  std::cout << res.get() << '\n';
}