本题的大意是一共有N个放格排列，每一个排列都可以有M种颜色，需要求解涂有相同颜色的对数不超过K对，可以考虑从N个中选择i个相邻的元素是一样的，这个i的范围是从0～k，之后可以发现第一个一定是M种选择，剩下的不同颜色的选择是$(M-1)^(N-1-i)$需要注意的是除法没有取模，所以需要使用到逆元

#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<cstring>
#include<array>
#include<queue>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
using i64=long long;
//using i128=__int128;
//const i64 INF=1e18;
const int mod=998244353;
//const int N=1e9+7;
const int N=2e5+10;
i64 fact[N],invfact[N];
i64 qmi(i64 a,i64 b){
    i64 res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void init(){
    fact[0]=invfact[0]=1;
    for(int i=1;i<=N;i++)fact[i]=i*fact[i-1]%mod;
    invfact[N]=qmi(fact[N],mod-2)%mod;
    for(int i=N-1;i>=0;i--){
        invfact[i]=invfact[i+1]*(i+1)%mod;
    }
}
void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    i64 ans=0;
    for(int i=0;i<=k;i++){
        if(n-i-1<0)break;
        ans=(ans+m*qmi(m-1,n-i-1)%mod*fact[n-1]%mod*invfact[i]%mod*invfact[n-i-1]%mod)%mod;
    }
    cout<<ans<<'\n';
}
int main(){
    init();
    int _=1;
    //cin>>_;
    while(_--)solve();
    return 0;
}