辺の重みを \(0\) 以上 \(M\) 未満として考え，最後に \((N-1)\times M^{N(N-1)/2}\) を加えることにします．

辺の重みが \(0\) 以上 \(M\) 未満の整数であるような連結グラフ \(G\) に対して，その最小全域木の重みの和は \(G_k\) を \(G\) の辺のうち重みが \(k\) 未満であるものからなる（重みなし）グラフ，\(c(G_k)\) を \(G_k\) の連結成分数として， \(\displaystyle \sum_{k=1}^{M} c(G_k)-M\) と表されます．

\(S_N\) を辺の重みが \(0\) 以上 \(M\) 未満であるような \(N\) 頂点完全グラフすべての集合，\(C(G_k)\) を \(G_k\) の連結成分の集合として，求める答えは

\[\displaystyle \sum_{G\in S_N}\sum_{k=1}^{M}c(G_k)-M=-M\times M^{N(N-1)/2}+\sum_{k=1}^{M}\sum_{G\in S_N}c(G_k)=-M\times M^{N(N-1)/2}+\sum_{k=1}^{M}\sum_{G\in S_N}\sum_{H\in C(G_k)}1\]

です．（\(c(G_k)=|C(G_k)|\) を用いています．）以下では各 \(k\) に対して \(\displaystyle \sum_{G\in S_N}\sum_{H\in C(G_k)}1\) を求める方法を導出します．

（ここまでのお気持ち：答えへの寄与を辺の重みに注目して分解することで 重みなし の 連結グラフ の数え上げ問題に帰着でき，数えやすくしています．）

\(H\) を固定して考えると（\(H\) は \(N\) 頂点完全グラフの部分グラフのうち連結であるものです），\(H\in C(G_k)\) となるような \(G\in S_N\) の個数は，\(V(H)\) を \(H\) の頂点集合，\(m(H)\) を \(H\) の辺の本数として

\[(M-k)^{|V(H)|(|V(H)|-1)/2-m(H)}\times k^{m(H)}\times (M-k)^{|V(H)|(N-|V(H)|)}\times M^{(N-|V(H)|)(N-|V(H)|-1)/2}\]

個です．これは，条件を満たす \(G\) の各辺の重みを考えたとき，両端が \(V(H)\) に含まれる辺ならば， \(H\) に含まれるものについては \(k\) 未満，含まれないものについては \(k\) 以上であり，また \(V(H)\) と \(\{1,2,\ldots,N\}\setminus V(H)\) の間にある辺であれば \(k\) 以上，両端が \(\{1,2,\ldots,N\}\setminus V(H)\) に含まれる辺であれば任意であることから従います．

よって主客転倒により（\(H\) に注目して式を変形することで）

\[\displaystyle \sum_{G\in S_N}\sum_{H\in C(G_k)}1=\sum_{H}(M-k)^{|V(H)|(|V(H)|-1)/2-m(H)}\times k^{m(H)}\times (M-k)^{|V(H)|(N-|V(H)|)}\times M^{(N-|V(H)|)(N-|V(H)|-1)/2}\]

です．\(H\) のうち頂点数が \(s\) であるものは \(H\) のうち頂点集合が \(\{1,2,\ldots,s\}\) であるものの \(\dbinom{N}{s}\) 倍あるので，\(H\) のうち頂点集合が \(\{1,2,\ldots,s\}\) であるもののすべてに対する \((M-k)^{|V(H)|(|V(H)|-1)/2-m(H)}\times k^{m(H)}\) の総和を \(f(s)\) とすれば

\[\displaystyle \sum_{H}(M-k)^{|V(H)|(|V(H)|-1)/2-m(H)}\times k^{m(H)}\times (M-k)^{|V(H)|(N-|V(H)|)}\times M^{(N-|V(H)|)(N-|V(H)|-1)/2}=\sum_{s=1}^N \binom{N}{s}f(s)\times (M-k)^{s(N-s)}\times M^{(N-s)(N-s-1)/2}\]

となります．

結局 \(f(s)\) が \(s=1,2,\ldots,N\) に対して求められれば良いことになります．これは ABC213G の解説にあるような連結グラフの数え上げと同様に考えることができ，\(f(s)=M^{s(s-1)/2}-\displaystyle\sum_{i=1}^{s-1}f(i)\dbinom{s-1}{i-1}(M-k)^{i(s-i)}M^{(s-i)(s-i-1)/2}\) が成り立ちます．この式に基づいて計算することで \(f(1),f(2),\ldots,f(N)\) を \(O(N^2)\) で求めることができます．

以上を \(k=1,2,\ldots,M\) それぞれについて行うことで，答えを \(O(N^2M)\) で求めることができます．

#include <bits/stdc++.h>
using namespace std;

#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;

mint binom[510][510];
mint POW[510][150000];

int main() {
  for (int i = 0; i < 510; i++) {
    binom[i][0] = 1;
    binom[i][i] = 1;
    for (int j = 1; j < i; j++) binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
    POW[i][0] = 1;
    for (int j = 1; j < 150000; j++) POW[i][j] = POW[i][j - 1] * i;
  }
  int n, m;
  cin >> n >> m;
  mint ans = (n - 1 - m) * POW[m][n * (n - 1) / 2];
  for (int k = 1; k <= m; k++) {
    vector<mint> f(n + 1, 0);
    for (int s = 1; s <= n; s++) {
      f[s] = POW[m][s * (s - 1) / 2];
      for (int i = 1; i < s; i++) f[s] -= f[i] * binom[s - 1][i - 1] * POW[m - k][i * (s - i)] * POW[m][(s - i) * (s - i - 1) / 2];
      ans += binom[n][s] * f[s] * POW[m - k][s * (n - s)] * POW[m][(n - s) * (n - s - 1) / 2];
    }
  }
  cout << ans.val() << endl;
}