#include using namespace std; template struct modint { modint():value(0){} modint(long long v) { long long x=(long long)(v%m()); if(x<0)x+=m(); value=x; } static modint raw(long long v) { modint x; x.value=v; return x; } static constexpr long long mod()noexcept{return m();} long long val()const{return value;} modint& operator++() { value++; if(value==m())value=0; return *this; } modint& operator--() { if(value==0)value=m(); value--; return *this; } modint operator++(int) { modint res=*this; ++*this; return res; } modint operator--(int) { modint res=*this; --*this; return res; } modint& operator+=(const modint& a) { value+=a.value; if(value>=m())value-=m(); return *this; } modint& operator-=(const modint& a) { value-=a.value; if(value<0)value+=m(); return *this; } modint& operator*=(const modint& a) { unsigned long long x=value; x*=a.value; x%=m(); if(x<0)x+=m(); value=x; return *this; } modint& operator/=(const modint& a) { return *this=(*this)*a.inv(); } modint operator+()const{return *this;} modint operator-()const{return modint()-*this;} modint pow(long long n)const { modint x=*this,res=1; while(n) { if(n&1)res*=x; x*=x; n>>=1; } return res; } modint inv()const { long long a=value,b=m(),u=1,v=0; while(b) { long long t=a/b; a-=t*b; swap(a,b); u-=t*v; swap(u,v); } return modint(u); } friend modint operator+(const modint& a, const modint& b) { modint res=a; res+=b; return res; } friend modint operator-(const modint& a, const modint& b) { modint res=a; res-=b; return res; } friend modint operator*(const modint& a, const modint& b) { modint res=a; res*=b; return res; } friend modint operator/(const modint& a, const modint& b) { modint res=a; res/=b; return res; } friend bool operator==(const modint& a, const modint& b) { return a.value==b.value; } friend bool operator!=(const modint& a, const modint& b) { return a.value!=b.value; } private: long long value; static constexpr long long m(){return mod_;} }; template struct Number_Theoretic_Transform { static vectordw,dw_inv; static int log; static mint root; static void ntt(vector& f) { init(); const int n=f.size(); for(int m=n;m>>=1;) { mint w=1; for(int s=0,k=0;s& f, bool flag=true) { init(); const int n=f.size(); for(int m=1;m>=1; log++; } dw.resize(log); dw_inv.resize(log); for(int i=0;i>(i+2)); dw_inv[i]=dw[i].inv(); } } }; template vectorNumber_Theoretic_Transform::dw=vector(); template vectorNumber_Theoretic_Transform::dw_inv=vector(); template int Number_Theoretic_Transform::log=0; template mint Number_Theoretic_Transform::root=mint(3); template struct Formal_Power_Series:vector { using FPS=Formal_Power_Series; using vector::vector; using NTT=Number_Theoretic_Transform; void ntt(){NTT::ntt(*this);} void intt(bool flag=true){NTT::intt(*this,flag);} FPS &operator+=(const mint& r) { if(this->empty())this->resize(1); (*this)[0]+=r; return *this; } FPS &operator-=(const mint& r) { if(this->empty())this->resize(1); (*this)[0]-=r; return *this; } FPS &operator*=(const mint& r) { for(mint &x:*this)x*=r; return *this; } FPS &operator/=(const mint& r) { mint invr=r.inv(); for(mint &x:*this)x*=invr; return *this; } FPS operator+(const mint& r)const{return FPS(*this)+=r;} FPS operator-(const mint& r)const{return FPS(*this)-=r;} FPS operator*(const mint& r)const{return FPS(*this)*=r;} FPS operator/(const mint& r)const{return FPS(*this)/=r;} FPS& operator+=(const FPS& f) { if(this->size()resize(f.size()); for(int i=0;i<(int)f.size();i++)(*this)[i]+=f[i]; return *this; } FPS& operator-=(const FPS& f) { if(this->size()resize(f.size()); for(int i=0;i<(int)f.size();i++)(*this)[i]-=f[i]; return *this; } FPS& operator*=(const FPS& f) { *this=convolution(*this,f); return *this; } FPS& operator/=(const FPS& f) { return *this*=f.inv(); } FPS& operator%=(const FPS& f) { *this-=this->div(f)*f; this->shrink(); return *this; } FPS operator+(const FPS& f)const{return FPS(*this)+=f;} FPS operator-(const FPS& f)const{return FPS(*this)-=f;} FPS operator*(const FPS& f)const{return FPS(*this)*=f;} FPS operator/(const FPS& f)const{return FPS(*this)/=f;} FPS operator%(const FPS& f)const{return FPS(*this)%=f;} FPS operator-()const { FPS res(this->size()); for(int i=0;i<(int)this->size();i++)res[i]-=(*this)[i]; return res; } FPS div(FPS f) { if(this->size()size()-f.size()+1; return (rev().pre(n)*f.rev().inv(n)).pre(n).rev(n); } FPS pre(int deg)const { return FPS(begin(*this),begin(*this)+min((int)this->size(),deg)); } FPS rev(int deg=-1)const { FPS res(*this); if(deg!=-1)res.resize(deg,0); reverse(begin(res),end(res)); return res; } void shrink() { while(!this->empty()&&this->back()==0)this->pop_back(); } FPS dot(FPS f)const { int n=min(this->size(),f.size()); FPS res(n); for(int i=0;i>(int deg)const { if((int)this->size()<=deg)return{}; FPS res(*this); res.erase(res.begin(),res.begin()+deg); return res; } FPS& operator>>=(int deg) { return *this=*this>>(deg); } mint operator()(const mint& r) { mint res=0,powr=1; for(auto x:*this) { res+=x*powr; powr*=r; } return res; } FPS diff()const { int n=this->size(); FPS res(max(0,n-1)); for(int i=1;isize(); FPS res(n+1); res[0]=0; for(int i=0;isize(); if(deg==-1)deg=n; FPS res(deg); res[0]={(*this)[0].inv()}; for(int d=1;dsize(); vectorinv; inv.reserve(deg+1); inv.push_back(mint::raw(0)); inv.push_back(mint::raw(1)); auto inplace_integral=[&](FPS& f)->void { int n=f.size(); long long mod=mint::mod(); while(inv.size()<=f.size()) { int i=inv.size(); inv.push_back((-inv[mod%i])*(mod/i)); } f.insert(begin(f),mint::raw(0)); for(int i=1;i<=n;i++)f[i]*=inv[i]; }; auto inplace_diff=[](FPS& f)->void { if(f.empty())return; f.erase(begin(f)); mint cef=1; for(int i=0;i<(int)f.size();i++) { f[i]*=cef; cef++; } }; FPS b={1,1size()?(*this)[1]:0}; FPS c={1},z1,z2={1,1}; for(int m=2;msize()),m)); inplace_diff(x); x.push_back(mint::raw(0)); x.ntt(); x=x.dot(y); x.intt(); x-=b.diff(); x.resize(2*m); for(int i=0;isize()),2*m);i++)x[i]+=(*this)[i]; fill(begin(x),begin(x)+m,mint::raw(0)); x.ntt(); x=x.dot(y); x.intt(); b.insert(end(b),begin(x)+m,end(x)); } return FPS{begin(b),begin(b)+deg}; } FPS log(int deg=-1)const { assert((*this)[0]==1); int n=this->size(); if(deg==-1)deg=n; return (this->diff()*this->inv()).pre(deg-1).integral(); } FPS pow(long long k, int deg=-1)const { if(deg==-1)deg=this->size(); if(k==0) { FPS res(deg); res[0]=mint::raw(1); return res; } FPS res=*this; int cnt0=0; while(cnt0(deg-1)/k) { FPS res(deg); return res; } res=res>>cnt0; deg-=cnt0*k; res=((res/res[0]).log(deg)*k).exp(deg)*res[0].pow(k); res=res<<(cnt0*k); return res.pre(deg); } FPS taylor_shift(mint c) { int n=this->size(); FPS fact(n),fact_inv(n); { // calc fact and fact inv fact[0]=1; for(int i=1;i=1;i--)fact_inv[i-1]=i*fact_inv[i]; } FPS res(*this); res=res.dot(fact); res=res.rev(); FPS bs(n,mint::raw(1)); for(int i=1;imultipoint_evaluation(vector&x) { if(x.empty())return{}; int m=x.size(),n=1; if(this->size()==0){return vector(m,0);} if(this->size()==1){return vector(m,(*this)[0]);} while(m>n)n<<=1; vectorf(n<<1,FPS({mint(1)})); for(int i=0;i0;i--)f[i]=f[i<<1]*f[(i<<1)|1]; f[1]=(*this)%f[1]; for(int i=2;i>1]%f[i]; vectorres(m); for(int i=0;i struct combination { combination(int n=0):inner_fac(1,1),inner_finv(1,1){init(n);} mint fac(int n) { init(n); return inner_fac[n]; } mint finv(int n) { init(n); return inner_finv[n]; } mint inv(int n) { if(n==0)return 0; init(n); return inner_fac[n-1]*inner_finv[n]; } mint C(int n, int r) { if(r<0)return 0; if(n<0) { n=-n; mint res=C(n-1+r,r); if(r&1)res=-res; return res; } if(ninner_fac,inner_finv; void init(int n) { int sz=inner_fac.size(); if(sz>n)return; n=min(max(n,2*sz),bound); inner_fac.resize(n+1); inner_finv.resize(n+1); for(int i=sz;i<=n;i++)inner_fac[i]=inner_fac[i-1]*i; inner_finv[n]=inner_fac[n].inv(); for(int i=n;i>sz;i--)inner_finv[i-1]=inner_finv[i]*i; } }; using mint=modint<998244353>; using FPS=Formal_Power_Series; combinationC; vectorstirling2(int n, int k) { FPS f(n-k+1); for(int i=0;i<=n-k;i++)f[i]=C.finv(i+1); f=f.pow(k); f*=C.finv(k); for(int i=0;i<=n-k;i++)f[i]*=C.fac(i+k); vectorres(n+1); for(int i=k;i<=n;i++)res[i]=f[i-k]; return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N,M,K; cin>>N>>M>>K; auto S=stirling2(N,K); mint ans=0; for(int n=K;n<=N;n++)ans+=C.C(N,n)*C.C(M,K)*mint(M).pow(N-n)*C.fac(K)*S[n]; cout<