// #define _GLIBCXX_DEBUG // for STL debug (optional) #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long int; using int64 = long long int; template void chmax(T &a, T b) {a = max(a, b);} template void chmin(T &a, T b) {a = min(a, b);} template void chadd(T &a, T b) {a = a + b;} int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; const int INF = 1LL << 29; const ll LONGINF = 1LL << 60; const ll MOD = 998244353LL; //BEGIN CUT HERE template struct Mint{ static constexpr T mod = MOD; T v; Mint():v(0){} Mint(signed v):v(v){} Mint(long long t){v=t%MOD;if(v<0) v+=MOD;} Mint pow(long long k){ Mint res(1),tmp(v); while(k){ if(k&1) res*=tmp; tmp*=tmp; k>>=1; } return res; } static Mint add_identity(){return Mint(0);} static Mint mul_identity(){return Mint(1);} Mint inv(){return pow(MOD-2);} Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;} Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;} Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;} Mint& operator/=(Mint a){return (*this)*=a.inv();} Mint operator+(Mint a) const{return Mint(v)+=a;} Mint operator-(Mint a) const{return Mint(v)-=a;} Mint operator*(Mint a) const{return Mint(v)*=a;} Mint operator/(Mint a) const{return Mint(v)/=a;} Mint operator-() const{return v?Mint(MOD-v):Mint(v);} bool operator==(const Mint a)const{return v==a.v;} bool operator!=(const Mint a)const{return v!=a.v;} bool operator <(const Mint a)const{return v constexpr T Mint::mod; template ostream& operator<<(ostream &os,Mint m){os< struct NTT{ static constexpr int md = bmds(X); static constexpr int rt = brts(X); using M = Mint; vector< vector > rts,rrts; void ensure_base(int n){ if((int)rts.size()>=n) return; rts.resize(n);rrts.resize(n); for(int i=1;i &as,bool f){ int n=as.size(); assert((n&(n-1))==0); ensure_base(n); for(int i=0,j=1;j+1>1;k>(i^=k);k>>=1); if(i>j) swap(as[i],as[j]); } for(int i=1;i multiply(vector as,vector bs){ int need=as.size()+bs.size()-1; int sz=1; while(sz multiply(vector as,vector bs){ vector am(as.size()),bm(bs.size()); for(int i=0;i<(int)am.size();i++) am[i]=M(as[i]); for(int i=0;i<(int)bm.size();i++) bm[i]=M(bs[i]); vector cm=multiply(am,bm); vector cs(cm.size()); for(int i=0;i<(int)cs.size();i++) cs[i]=cm[i].v; return cs; } }; template constexpr int NTT::md; template constexpr int NTT::rt; //BEGIN CUT HERE template class Enumeration{ using M = M_; protected: static vector fact,finv,invs; public: static void init(int n){ n=min(n,M::mod-1); int m=fact.size(); if(n=m;i--) finv[i-1]=finv[i]*M(i); for(int i=m;i<=n;i++) invs[i]=finv[i]*fact[i-1]; } static M Fact(int n){ init(n); return fact[n]; } static M Finv(int n){ init(n); return finv[n]; } static M Invs(int n){ init(n); return invs[n]; } static M C(int n,int k){ if(n vector Enumeration::fact=vector(); template vector Enumeration::finv=vector(); template vector Enumeration::invs=vector(); template struct FormalPowerSeries : Enumeration { using M = M_; using super = Enumeration; using super::fact; using super::finv; using super::invs; using Poly = vector; using Conv = function; Conv conv; FormalPowerSeries(Conv conv):conv(conv){} Poly pre(const Poly &as,int deg){ return Poly(as.begin(),as.begin()+min((int)as.size(),deg)); } Poly add(Poly as,Poly bs){ int sz=max(as.size(),bs.size()); Poly cs(sz,M(0)); for(int i=0;i<(int)as.size();i++) cs[i]+=as[i]; for(int i=0;i<(int)bs.size();i++) cs[i]+=bs[i]; return cs; } Poly sub(Poly as,Poly bs){ int sz=max(as.size(),bs.size()); Poly cs(sz,M(0)); for(int i=0;i<(int)as.size();i++) cs[i]+=as[i]; for(int i=0;i<(int)bs.size();i++) cs[i]-=bs[i]; return cs; } Poly mul(Poly as,Poly bs){ return conv(as,bs); } Poly mul(Poly as,M k){ for(auto &a:as) a*=k; return as; } bool is_zero(Poly as){ return as==Poly(as.size(),0); } void shrink(Poly &as){ assert(not is_zero(as)); while(as.back()==M(0)) as.pop_back(); } // F(0) must not be 0 Poly inv(Poly as,int deg); // not zero Poly div(Poly as,Poly bs); // not zero Poly mod(Poly as,Poly bs); // F(0) must be 1 Poly sqrt(Poly as,int deg); Poly diff(Poly as); Poly integral(Poly as); // F(0) must be 1 Poly log(Poly as,int deg); // F(0) must be 0 Poly exp(Poly as,int deg); // not zero Poly pow(Poly as,long long k,int deg); // x <- x + c Poly shift(Poly as,M c); }; template vector FormalPowerSeries::inv(Poly as,int deg){ assert(as[0]!=M(0)); Poly rs({M(1)/as[0]}); for(int i=1;i> N >> M >> K; NTT<2> ntt; using mint = NTT<2>::M; auto conv = [&](auto as, auto bs) { return ntt.multiply(as, bs); }; FormalPowerSeries FPS(conv); Enumeration comb; comb.init(200010); // dp[k][i] = dp[k][i-1] * k + dp[k-1][i-1] * (K-k+1) // F = F*k*x + F'*(K-k+1)*x // F(1-k*x) = F'(K-k+1)*x // F = F'(K-k+1)*x / (1-k*x) // F = \Pi_{k=1}^{K} (K-k+1)*x / \Pi_{k=1}^{K} (1-k*x) // F = K!*x / \Pi_{k=1}^{K} (1-k*x) // 多項式の inv があれば OK auto go = [&](auto &&self, int l, int r) -> vector { if(r - l == 1) { return {mint(1), mint(-r)}; } int m = (l + r) / 2; return ntt.multiply(self(self, l, m), self(self, m, r)); }; vector A(K+1); A[K] = mint(1); for(int i=1; i<=K; i++) A[K] *= mint(i); vector B = FPS.inv(go(go, 0, K), N+1); vector X = ntt.multiply(A, B); mint ans(0); for(int i=K; i<=N; i++) { mint ways = X[i]; ways *= comb.C(M, K); ways *= comb.H(N-i, i+1) * mint(M).pow(N-i); ans += ways; } cout << ans << endl; return 0; }