首先多项式科技显然可做。

但是为什么这个 Code 是对的？

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
signed main() {
    int n, k; cin >> n >> k;
    if(n == 1) return puts("0") & 0;
    vector<int> a(n + 1);
    a[1] = 1;
    int s = 1;
    for(int i = 2; i < n; i++) {
        s = s * k % mod;
        a[i] = (a[i - 1] + s * i % mod) % mod;
    }
    cout << a[n - 1] * ((k + 1) * k % mod * (k - 1) % mod * 166374059 % mod) % mod;
    return 0;
}

甚至在 CF Announcement 下面还有很给出了另一个更加简洁的答案：

$\frac{((N-1)K^N -NK^{N-1}+1)K(K+1)}{6(K-1)}$

怎么证明？求助qwq