Submission #13111548

---

Source Code Expand

//This is the Property of Rishabh Agarwal
#include <bits/stdc++.h>
#define F first
#define S second
#define MAX 10000003
using namespace std;

typedef long long int ll;
const ll mod =998244353;
ll power(ll a,ll b){
    if(b==0){
        return 1;
    }
    ll temp=power(a,b/2)%mod;
    if(b%2==0){
        return (temp*temp)%mod;
    }
    else{
        return ((a*temp)%mod*temp)%mod;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,m,k;
    cin>>n>>m>>k;
    ll ans=0;
    ans+=((m%mod)*(power(m-1,n-1)%mod))%mod;
    ans%=mod;
    ll count = 1;
    for(ll x=1; x<=k; x++){
        count*=(n-x);
        //count%=mod;
        count/=x;
        count%=mod;
        //cout<<count<<" ";
        ans+=((((count%mod)*(m%mod))%mod)*(power(m-1,n-1-x)%mod))%mod;
        ans%=mod;
    }
    cout<<ans<<"\n";
    return 0;
}

Submission Info

Judge Result