#include template using vc = std::vector; struct CustomHash { static constexpr uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } static constexpr size_t append(size_t x, size_t y) { return x ^ (y >> 1) ^ ((y & 1) << (sizeof(size_t) * 8 - 1)); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } template size_t operator()(std::pair const &p) const { return append((*this)(p.first), (*this)(p.second)); } template size_t operator()(std::tuple const &tp) const { size_t ret = 0; std::apply( [&](Ts const &...targs) { ((ret = append(ret, (*this)(targs))), ...); }, tp); return ret; } template < class Tp, std::enable_if_t().begin()), typename Tp::iterator>::value && std::is_same().end()), typename Tp::iterator>::value> * = nullptr> size_t operator()(Tp const &tp) const { size_t ret = 0; for (auto &&i : tp) ret = append(ret, (*this)(i)); return ret; } }; using u32 = uint32_t; using i64 = int64_t; #define for_(i, l, r, vars...) \ for (std::make_signed_t i = (l), i##end = (r), ##vars; \ i <= i##end; \ ++i) #define all_(a) (a).begin(), (a).end() template constexpr auto chkmin(Tp &a, Tp b) -> bool { return b < a ? a = b, true : false; } template constexpr auto chkmax(Tp &a, Tp b) -> bool { return a < b ? a = b, true : false; } template constexpr auto ispow2(Tp i) -> bool { return i && (i & -i) == i; } #define TPL_SIZE_(Tuple) std::tuple_size_v> namespace tuple_detail_ { template constexpr auto subtuple_impl_(Tuple &&t, std::index_sequence) { return std::make_tuple(std::get(t)...); } template constexpr auto apply2_impl_(BinOp &&f, Tuple &&lhs, Tuple &&rhs, std::index_sequence) { return std::make_tuple( std::forward(f)(std::get(lhs), std::get(rhs))...); } } // namespace tuple_detail_ template constexpr auto subtuple(Tuple &&t) { static_assert(Begin <= TPL_SIZE_(Tuple) && Len <= TPL_SIZE_(Tuple) && Begin + Len <= TPL_SIZE_(Tuple), "Out of range"); return tuple_detail_::subtuple_impl_(t, std::make_index_sequence()); } template constexpr auto tuple_push(Tp &&v, Tuple &&t) { static_assert(TPL_SIZE_(Tuple) > 0, "Pop from empty tuple"); return std::tuple_cat(subtuple<0, Pos>(t), std::make_tuple(v), subtuple(t)); } template constexpr auto tuple_push_front(Tp &&v, Tuple &&t) { return tuple_push<0>(v, t); } template constexpr auto tuple_push_back(Tp &&v, Tuple &&t) { return tuple_push(v, t); } template constexpr auto tuple_pop(Tuple &&t) { static_assert(TPL_SIZE_(Tuple) > 0, "Pop from empty tuple"); return std::tuple_cat(subtuple<0, Pos>(t), subtuple(t)); } template constexpr auto tuple_pop_front(Tuple &&t) { return tuple_pop<0>(t); } template constexpr auto tuple_pop_back(Tuple &&t) { return tuple_pop(t); } template constexpr auto apply2(BinOp &&f, Tuple &&lhs, Tuple &&rhs) { return tuple_detail_::apply2_impl_( f, lhs, rhs, std::make_index_sequence()); } #define OO_PTEQ_(op) \ template \ constexpr auto operator op(std::pair lhs, \ const std::pair &rhs) { \ return std::pair{lhs.first op rhs.first, \ lhs.second op rhs.second}; \ } \ template \ constexpr auto operator op(std::tuple const &lhs, \ std::tuple const &rhs) { \ return apply2([](auto &&l, auto &&r) { return l op r; }, lhs, rhs); \ } \ template \ constexpr std::pair &operator op##=(std::pair &lhs, \ const std::pair &rhs) { \ lhs.first op## = rhs.first; \ lhs.second op## = rhs.second; \ return lhs; \ } \ template \ constexpr auto operator op##=(std::tuple &lhs, \ const std::tuple &rhs) { \ return lhs = lhs op rhs; \ } OO_PTEQ_(+) OO_PTEQ_(-) OO_PTEQ_(*) OO_PTEQ_(/) OO_PTEQ_(%) OO_PTEQ_(&) OO_PTEQ_(|) OO_PTEQ_(^) OO_PTEQ_(<<) OO_PTEQ_(>>) #undef OO_PTEQ_ #undef TPL_SIZE_ template std::istream &operator>>(std::istream &is, std::pair &p) { return is >> p.first >> p.second; } template std::ostream &operator<<(std::ostream &os, const std::pair &p) { return os << p.first << ' ' << p.second; } template std::istream &operator>>(std::istream &is, std::tuple &p) { std::apply([&](Ts &...targs) { ((is >> targs), ...); }, p); return is; } template std::ostream &operator<<(std::ostream &os, const std::tuple &p) { std::apply( [&](Ts const &...targs) { std::size_t n{0}; ((os << targs << (++n != sizeof...(Ts) ? " " : "")), ...); }, p); return os; } template < class Ch, class Tr, class Ct, std::enable_if_t().begin()), typename Ct::iterator>::value && std::is_same().end()), typename Ct::iterator>::value> * = nullptr> std::basic_ostream &operator<<(std::basic_ostream &os, const Ct &x) { if (x.begin() == x.end()) return os; for (auto it = x.begin(); it != x.end() - 1; ++it) os << *it << ' '; os << x.back(); return os; } const u32 OFFSET = 5; const u32 N = 5e5 + OFFSET; const i64 MOD = 998244353; using namespace std; constexpr int64_t qpow(int64_t a, int64_t b, int64_t mod) { int64_t res(1); a %= mod; for (; b; b >>= 1, (a *= a) %= mod) if (b & 1) (res *= a) %= mod; return res; } constexpr int64_t inverse(int64_t n, int64_t mod) { int64_t b = mod, m0 = 0; for (int64_t q = 0, _ = 0, m1 = 1; n;) { _ = b - n * (q = b / n); b = n; n = _; _ = m0 - m1 * q; m0 = m1; m1 = _; } return (m0 + (m0 < 0 ? mod / b : 0)) % mod; } std::vector fact, inv_fact; void init_fact(int64_t n = N, int64_t mod = MOD) { std::vector ffact(n); fact.resize(n * 2); inv_fact.resize(n); ffact[0] = fact[0] = inv_fact[0] = fact[1] = inv_fact[1] = 1; for (size_t i = 2; i < std::min(mod, n * 2); ++i) fact[i] = fact[i - 1] * i % mod; for (size_t i = 1; i < std::min(mod, n); ++i) ffact[i] = ffact[i - 1] * fact[i] % mod; int64_t _ = inverse(ffact[std::min(mod, n) - 1], mod); for (ptrdiff_t i = std::min(mod, n) - 1; i > 1; --i) { inv_fact[i] = _ * ffact[i - 1] % mod; _ = _ * fact[i] % mod; } } constexpr int64_t mCn(int m, int n, int64_t mod = MOD) { return m < n || n < 0 ? 0 : fact[m] * inv_fact[n] % mod * inv_fact[m - n] % mod; } int64_t lagrange_interp_fixed_key(std::vector const &v, uint64_t x, int64_t mod) { const size_t n = v.size(); if (x < n) return v[x]; std::vector ifact(n); ifact[0] = ifact[1] = 1; for (size_t i = 2; i < n; ++i) ifact[i] = mod - mod / i * ifact[mod % i] % mod; for (size_t i = 3; i < n; ++i) (ifact[i] *= ifact[i - 1]) %= mod; std::vector pre(n); for (size_t i = 0; i < n; ++i) pre[i] = x - i; for (size_t i = 1; i < n; ++i) (pre[i] *= pre[i - 1]) %= mod; std::vector suc(n); for (size_t i = 0; i < n; ++i) suc[i] = x - i; for (ptrdiff_t i = n - 2; i >= 0; --i) (suc[i] *= suc[i + 1]) %= mod; int64_t ans = 0; for (size_t i = 0; i < n; ++i) { int64_t _ = v[i]; if (i) _ = _ * pre[i - 1] % mod; if (i + 1 < n) _ = _ * suc[i + 1] % mod; _ = _ * ifact[i] % mod * ifact[n - i - 1] % mod; ans = (ans + ((n - i) % 2 ? _ : mod - _)) % mod; } return ans; } auto solve([[maybe_unused]] int t_ = 0) -> void { i64 n, k; cin >> n >> k; i64 ans = 0; vc f(n + 3); for_(i, 1, n) for_(x, 0, i - 1) for_(y, x + 1, n - i) for_(t, 1, n + 2) (f[t] += t * mCn(i - 1, x) % MOD * qpow(t - 1, x, MOD) % MOD * qpow(k - t + 1, i - x - 1, MOD) % MOD * mCn(n - i, y) % MOD * qpow(k - t, y, MOD) % MOD * qpow(t, n - i - y, MOD) % MOD) %= MOD; partial_sum(all_(f), f.begin(), [](i64 x, i64 y) { return (x + y) % MOD; }); cout << lagrange_interp_fixed_key(f, k, MOD); } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int i_ = 0; init_fact(); solve(i_); return 0; }