1278F - Cards - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#define el << '\n'
#define nl cout << '\n'
#define cina(a,n) for (int i=0; i<n; i++) cin >> a[i]
#define ll long long
#define spc << ' '
#define forn(i,n) for (int i=0; i<n; i++)
#define forl(i,s,e) for (int i=s; i<e; i++)
#define MOD 1000000007
#define MOD2 998244353
#define pb push_back
#define ansyes cout << "YES\n"
#define ansno cout << "NO\n"
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<long long, long long>

ll power(ll a, ll b) {
    if (b==0) return 1;
    if (b%2) return (a*power(a,b-1))%MOD2;
    ll temp = power(a,b/2);
    return (temp*temp)%MOD2;
}

ll inv(ll a) {
    return power(a,MOD2-2);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,m; cin >> n >> m;
    ll k; cin >> k;
    ll dp[k+1][k+1];
    forn(i,k+1) forn(j,k+1) dp[i][j]=0;
    dp[0][0]=1;
    forn(i,k) {
        forn(j,k) {
            dp[i][j] %= MOD2;
            dp[i+1][j+1] += dp[i][j]*(n-j);
            dp[i+1][j] += dp[i][j]*j;
        }
        dp[i+1][k] += dp[i][k]*k;
    }
    ll ans=0;
    forl(i,1,k+1) {
        ans += (dp[k][i]%MOD2 * inv(power(m,i)));
        ans %= MOD2;
    } 
    cout << ans;
}