【題解】AtCoder ABC 167E – Colorful Blocks

#include <iostream>
using namespace std;

int n, m, k;

const int maxn = 400005;
const long long mod = 998244353;
long long pre[maxn];
long long inv[maxn];
long long prei[maxn];
void build(int n){
    pre[1] = pre[0] = 1, inv[1] = inv[0] = 1, prei[1] = prei[0] = 1;
    for(int i = 2 ; i <= n ; i++){
        pre[i] = pre[i-1] * i % mod;
        inv[i] = (mod - mod / i * inv[mod % i] % mod) % mod;
        prei[i] = prei[i-1] * inv[i] % mod;
    }
}
long long C(int n, int k){
   return pre[n] * prei[k] % mod * prei[n-k] % mod;
}
long long pm(int n,int p){
    long long ret = 1;
    long long now = n;
    while(p){
        if(p & 1){
            ret *= now;
            ret %= mod;
        }
        now *= now;
        now %= mod;
        p >>= 1;
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    build(n);
    long long ans = 0;
    for (int i = 0; i <= k; i++){
        ans += pm(m-1, n-i-1) * m % mod * C(n-1, n-i-1) % mod;
        ans %= mod;
    }
    cout << ans << "\n";
}