#ifndef LOCAL #define FAST_IO #endif // ============ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define OVERRIDE(a, b, c, d, ...) d #define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i) #define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i) #define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__) #define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i) #define ALL(x) begin(x), end(x) using namespace std; using u32 = unsigned int; using u64 = unsigned long long; using i32 = signed int; using i64 = signed long long; using f64 = double; using f80 = long double; template using Vec = vector; template bool chmin(T &x, const T &y) { if (x > y) { x = y; return true; } return false; } template bool chmax(T &x, const T &y) { if (x < y) { x = y; return true; } return false; } #ifdef INT128 using u128 = __uint128_t; using i128 = __int128_t; istream &operator>>(istream &is, i128 &x) { i64 v; is >> v; x = v; return is; } ostream &operator<<(ostream &os, i128 x) { os << (i64)x; return os; } istream &operator>>(istream &is, u128 &x) { u64 v; is >> v; x = v; return is; } ostream &operator<<(ostream &os, u128 x) { os << (u64)x; return os; } #endif [[maybe_unused]] constexpr i32 INF = 1000000100; [[maybe_unused]] constexpr i64 INF64 = 3000000000000000100; struct SetUpIO { SetUpIO() { #ifdef FAST_IO ios::sync_with_stdio(false); cin.tie(nullptr); #endif cout << fixed << setprecision(15); } } set_up_io; // ============ #ifdef DEBUGF #else #define DBG(x) (void) 0 #endif // ============ // ============ #include #include #include namespace poly { using Mint = atcoder::modint998244353; using Poly = std::vector; Poly add(Poly f, Poly g) { if (f.size() < g.size()) { std::swap(f, g); } for (int i = 0; i < (int)g.size(); ++i) { f[i] += g[i]; } return f; } Poly sub(Poly f, Poly g) { if (f.size() < g.size()) { std::swap(f, g); } for (int i = 0; i < (int)g.size(); ++i) { f[i] -= g[i]; } return f; } Poly mul(const Poly &f, const Poly &g) { return atcoder::convolution(f, g); } void dft(Poly &f) { atcoder::internal::butterfly(f); } void idft(Poly &f) { atcoder::internal::butterfly_inv(f); Mint inv = Mint::raw(f.size()).inv(); for (Mint &cf : f) { cf *= inv; } } } // namespace poly // ============ namespace poly { class Factorial { std::vector fac; std::vector ifac; public: Factorial() : fac(1, Mint::raw(1)), ifac(1, Mint::raw(1)) {} void reserve(int n) { int m = (int)fac.size() - 1; if (n <= m) { return; } fac.resize(n + 1); for (int i = m + 1; i <= n; ++i) { fac[i] = fac[i - 1] * Mint::raw(i); } ifac.resize(n + 1); ifac[n] = fac[n].inv(); for (int i = n - 1; i >= m; --i) { ifac[i] = ifac[i + 1] * Mint::raw(i + 1); } } Mint fact(int n) const { return fac[n]; } Mint inv_fact(int n) const { return ifac[n]; } Mint inv_n(int n) const { return ifac[n] * fac[n - 1]; } Mint binom(int n, int r) const { return fac[n] * ifac[r] * ifac[n - r]; } } factorial; } // namespace poly // ============ using namespace poly; Poly pow_of_fps(const Poly &f, i32 n) { // fps exp まだ移植できてないので log 2 つで... if (n == 0) { Poly g(f.size()); g[0] = Mint::raw(1); return g; } Poly g = pow_of_fps(f, n / 2); g = mul(g, g); g.resize(f.size()); if (n % 2 == 1) { g = mul(f, g); g.resize(f.size()); } return g; } int main() { i32 n, m; cin >> n >> m; if (m == 1) { cout << 0 << '\n'; exit(0); } factorial.reserve(n); Poly f(n + 1); REP(i, n + 1) { f[i] = factorial.inv_fact(i) * factorial.inv_fact(i); } Poly g = pow_of_fps(f, m - 2); // 1 と 2 が swap される回数を数える。 // この値を M(M-1)/2 倍すれば答えが求まる。 Mint ans; REP(i, 2, n + 1) { Mint c = g[n - i] * factorial.fact(n - i) * factorial.fact(n - i) * factorial.binom(n, i) * factorial.binom(n, i); Mint sub = Mint::raw(2).pow(2 * i - 3) * Mint::raw(i - 1); ans += c * sub; } ans *= Mint::raw(m) * Mint::raw(m - 1) / Mint::raw(2); cout << ans.val() << '\n'; }