Description
数学老师走啦，英语老师来上课啦
他的性格与众不同，又因为大家都是理科班的学生
他希望大家在数字母的过程中领悟英语的快乐
他用(m)种字母进行排列组合，
得到了所有不同的，长度为(n)的字符串
（不需要所有字母都出现在字符串中）
对于每个字符串(s)
定义(C(s))为(s)中出现次数最多的字母的出现次数
那么问题来了
所有的这些字符集大小为(m)，长度为(n)的字符串中
(C(s)=k)的有多少个呢
Input
一行三个整数(n,m,k)，分别表示字符集，长度和要求的(C(s))
Output
输出一行表示结果
答案对(998244353)取模
Sample Input
3 2 2
Sample Output
6
HINT
数据保证(k≤n)
对于10%的数据，(1≤n,m≤8)
对于30%的数据，(1≤n,m≤200)
对于50%的数据，(1≤n,m≤1000)
对于100%的数据，(1≤n,m≤50000)
样例解释：
假设样例中的两个字母为(a,b)
则满足条件的有(aab,aba,abb,baa,bab,bba)六个
Solution
先考虑一下大力dp，(f[i][j][k])表示确定完前(i)个字母的位置，占用了(s)中的(j)个位置，且此时(C(s)<=k)的方案数
那么最后的答案应该是(f[m][n][k]-f[m][n][k-1])
仔细观察一下这个dp式子，会发现这个dp其实跟(k)没有太大的关系（影响的只是枚举范围），而(i)这一维通过转移时候的继承是可以直接省掉的，然后又发现这个是个卷积的形式，那就大力构造一下多项式然后乘一波咯
我们定义(F_i(x)=sumlimits_{j=0}^{k}frac{f[i][j][k]}{j!}x^j)，(G(x)=sumlimits_{j=0}^{k}frac{1}{j!}x^j)，那么上面式子的(frac{f[i][j][k]}{j!})就可以看做(F_i(x))的(j)次项的系数（生成函数的意味。。？），其他的部分同理，我们可以得到这样的式子：
最后的(f[m][n][k])就是：(F_m(x))的(n)次项的系数*(n!)，(f[m][n][k-1])的计算同理，只要稍微改变一下(k)的值就好了，所以下面只讨论(f[m][n][k])的求法：
重新看回(F_i(x))的那个递推式，不难发现其实(F_m(x)=(F_0(x)G(x))^m)（一路推上来的嘛）
那就是做一个快速幂卷积就好了，注意一下每次乘完之后超过(n)的部分要赋成(0)
（初始化的话因为只有(f[0][0][k]=1)，所以(F_0(x)=1)）
代码大概长这个样子（NTT忘记swap这个错能犯一万年。。。菜菜发抖qwq）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define G 3
#define vct vector<int>
using namespace std;
const int MAXN=5*(1e4)+10,MOD=998244353;
int ksm(int x,int y);
namespace NTT{/*{{{*/
int W[MAXN*4][2],rev[MAXN*4];
int len,invlen,invg;
void init(){
invg=ksm(G,MOD-2);
for (int i=0;i<=17;++i){
W[1<<i][0]=ksm(G,(MOD-1)/(1<<i));
W[1<<i][1]=ksm(invg,(MOD-1)/(1<<i));
}
}
void prework(int n){
int bit=0;
for (len=1;len<n;len<<=1,++bit);
rev[0]=0;
for (int i=1;i<len;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
invlen=ksm(len,MOD-2);
}
void ntt(int *a,int op){
int w,w_n,u,t;
for (int i=0;i<len;++i)
if (rev[i]>i) swap(a[i],a[rev[i]]);
for (int step=2;step<=len;step<<=1){
w_n=op==-1?W[step][0]:W[step][1];
for (int st=0;st<len;st+=step){//< !!
w=1;
for (int i=0;i<(step>>1);++i){
t=1LL*a[st+i+(step>>1)]*w%MOD;
u=a[st+i];
a[st+i]=(1LL*u+t)%MOD;
a[st+i+(step>>1)]=(1LL*u+MOD-t)%MOD;
w=1LL*w*w_n%MOD;
}
}
}
if (op==1) return;
for (int i=0;i<len;++i)
a[i]=1LL*a[i]*invlen%MOD;
}
}/*}}}*/
int fac[MAXN],invfac[MAXN];
int base[MAXN*4],ret[MAXN*4];
int n,m,k;
void prework(int n);
void ksm_solve(int *a,int n,int y,int *ret);//n=len m=num k=appear times
int solve(int n,int m,int k);
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
#endif
scanf("%d%d%d",&n,&m,&k);
prework(n);
int ansk,ansk1;
ansk1=solve(n,m,k-1);
ansk=solve(n,m,k);
printf("%d
",(1LL*ansk+MOD-ansk1)%MOD);
}
int ksm(int x,int y){
int ret=1,base=x;
for (;y;y>>=1,base=1LL*base*base%MOD)
if (y&1) ret=1LL*ret*base%MOD;
return ret;
}
void prework(int n){
NTT::init();
NTT::prework((n+1)*2);
fac[0]=1;
for (int i=1;i<=n;++i) fac[i]=1LL*fac[i-1]*i%MOD;
invfac[n]=ksm(fac[n],MOD-2);
for (int i=n-1;i>=0;--i) invfac[i]=1LL*invfac[i+1]*(i+1)%MOD;
}
int solve(int n,int m,int k){
memset(base,0,sizeof(base));
memset(ret,0,sizeof(ret));
for (int i=0;i<=k;++i) base[i]=invfac[i];
ksm_solve(base,n,m,ret);
return 1LL*ret[n]*fac[n]%MOD;
}
void ksm_solve(int *a,int n,int y,int *ret){
ret[0]=1;
while (y){
NTT::ntt(a,1);
if (y&1){
NTT::ntt(ret,1);
for (int i=0;i<NTT::len;++i) ret[i]=1LL*ret[i]*a[i]%MOD;
NTT::ntt(ret,-1);
for (int i=n+1;i<NTT::len;++i) ret[i]=0;
}
for (int i=0;i<NTT::len;++i) a[i]=1LL*a[i]*a[i]%MOD;
NTT::ntt(a,-1);
for (int i=n+1;i<NTT::len;++i) a[i]=0;
y>>=1;
}
}