题目要求：
[sum_{x=0}^n binom{n}{x}x^kP^x(1-P)^{n-x}
]
其中(p=frac{1}{m})，这就要利用第二类斯特林数来推式子了。将(x^k)替换掉，具体方法可以看上一篇博客传送门。
大力推一波式子：
[sum_{x=0}^n binom{n}{x}x^kP^x(1-P)^{n-x}
]
[sum_{x=0}^n binom{n}{x}P^x(1-P)^{n-x}sum_{i=0}^ki!S(k,i)(x,i)
]
[sum_{i=0}^kS(k,i)i!sum_{x=i}^n binom{n}{x} binom{x}{i}P^x(1-P)^{n-x}
]
在组合数中有一个很重要的结论：
[ binom{n}{i} binom{i}{j}= binom{n}{j} binom{n-j}{i-j}
]
证明就是把组合数化成阶乘凑配一下。
接着往下推：
[sum_{i=0}^kS(k,i)i!sum_{x=i}^n binom{n}{i} binom{n-i}{x-i}P^x(1-P)^{n-x}
]
[sum_{i=0}^kS(k,i)frac{n!}{(n-i)!}P^isum_{x=i}^n binom{n-i}{n-x}P^{x-i}(1-P)^{n-x}
]
注意到:
[sum_{x=i}^n binom{n-i}{n-x}P^{x-i}(1-P)^{n-x}=1^{n-i}
]
所以最后的结果是：
[sum_{i=0}^kS(k,i)frac{n!}{(n-i)!}P^i
]
最后就(O(k^2))预处理出第二类斯特林数。
#include<bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define fi first
#define sd second
#define lson (nd<<1)
#define rson (nd+nd+1)
#define PB push_back
#define mid (l+r>>1)
#define MP make_pair
#define SZ(x) (int)x.size()
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
inline int read(){
int res=0, f=1;char ch=getchar();
while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
return res*f;
}
const int MAXN = 5'005;
const int MOD = 998244353;
void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;}
int mulmod(int a, int b){return 1ll*a*b%MOD;}
template<typename T>
void chmin(T& a, T b){if(a>b)a=b;}
template<typename T>
void chmax(T& a, T b){if(b>a)a=b;}
int powmod(int x,int y){
int res=1;
while(y){
if(y&1)
res=1ll*res*x%MOD;
x=1ll*x*x%MOD;
y>>=1;
}
return res;
}
int S[MAXN][MAXN];
int fac[MAXN],inv[MAXN];
void init(){
S[0][0]=1;
for(int i=1;i<=5000;++i){
for(int j=1;j<=i;++j){
S[i][j]=(1ll*S[i-1][j-1]+1ll*j*S[i-1][j])%MOD;
}
}
fac[0]=inv[0]=inv[1]=1;
for(int i=1;i<=5000;++i)fac[i]=1ll*i*fac[i-1]%MOD;
for(int i=2;i<=5000;++i)inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
for(int i=2;i<=5000;++i)inv[i]=1ll*inv[i]*inv[i-1]%MOD;
}
int x_(int x, int y){
int res=1;
for(int i=0;i<y;++i)res=1ll*res*(x-i)%MOD;
return res;
}
int main(){
init();
int n=read(),m=read(),k=read();
int P=powmod(m,MOD-2);
int res=0;
for(int i=0;i<=k;++i){
res+=1ll*S[k][i]*x_(n,i)%MOD*powmod(P,i)%MOD;
res%=MOD;
}
if(res<0)res+=MOD;
cout<<res;
return 0;
}