// 那就是希望。
// 即便需要取模，也是光明。

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
namespace ConstMod
{
template<const ullt p>
class mod_ullt
{
private:
    ullt v;
    inline ullt chg(ullt w){return(w<p)?w:w-p;}
    inline mod_ullt _chg(ullt w){mod_ullt ans;ans.v=(w<p)?w:w-p;return ans;}
public:
    mod_ullt():v(0){}
    mod_ullt(ullt v):v(v%p){}
    inline bol empty(){return!v;}
    inline ullt val(){return v;}
    inline ullt&operator()(){return v;}
    inline friend bol operator==(mod_ullt a,mod_ullt b){return a()==b();}
    inline friend bol operator!=(mod_ullt a,mod_ullt b){return a()!=b();}
    inline mod_ullt operator+(){return*this;}
    inline friend mod_ullt operator+(mod_ullt a,mod_ullt b){return a._chg(a()+b());}
    inline mod_ullt&operator+=(mod_ullt b){return*this=*this+b;}
    inline mod_ullt operator-(){return _chg(p-v);}
    inline friend mod_ullt operator-(mod_ullt a,mod_ullt b){return a+(-b);}
    inline mod_ullt&operator-=(mod_ullt b){return*this=*this-b;}
    inline friend mod_ullt operator*(mod_ullt a,mod_ullt b){return a()*b();}
    inline mod_ullt&operator*=(mod_ullt b){return*this=*this*b;}
    inline friend mod_ullt operator/(mod_ullt a,mod_ullt b){return a*b.inv();}
    inline mod_ullt&operator/=(mod_ullt b){return*this=*this/b;}
    friend mod_ullt operator^(mod_ullt a,ullt b)
    {
        mod_ullt v(1);
        while(b)
        {
            if(b&1)v*=a;
            a*=a,b>>=1;
        }
        return v;
    }
    inline mod_ullt&operator^=(ullt b){return*this=*this^b;}
    inline mod_ullt operator++(int){mod_ullt ans=*this;return v=chg(v+1),ans;}
    inline mod_ullt&operator++(){return v=chg(v+1),*this;}
    inline mod_ullt operator--(int){mod_ullt ans=*this;return v=chg(v+p-1),ans;}
    inline mod_ullt&operator--(){return v=chg(v+p-1),*this;}
    inline mod_ullt inv(){return(*this)^(p-2);}
    mod_ullt sqrt()
    {
        if(((*this)^((p-1)>>1))!=1)return 0;
        mod_ullt b(1);do b++;while((b^((p-1)>>1))==1);
        ullt t=p-1;uint s=0;while(!(t&1))s++,t>>=1;
        mod_ullt x=(*this)^((t+1)>>1),e=(*this)^t,w=inv();
        for(uint k=1;k<s;k++,e=w*x*x)if((e^(1llu<<(s-k-1)))!=1)x*=b^((1llu<<(k-1))*t);
        ullt ans=x();_min(ans,p-ans);return ans;
    }
    voi read()
    {
        v=0;chr c;do c=getchar();while(c>'9'||c<'0');
        do v=(c-'0'+v*10)%p,c=getchar();while(c>='0'&&c<='9');
    }
    voi print(chr endc='\0')
    {
        static chr C[20];uint tp=0;
        ullt w=v;do C[tp++]=w%10+'0',w/=10;while(w);
        while(tp--)putchar(C[tp]);
        if(endc)putchar(endc);
    }
    inline voi println(){print('\n');}
};
}
namespace NTT_POLY
{
template<const ullt p,const ullt g>
class poly_NTT
{
public:
    typedef ConstMod::mod_ullt<p>modint;
    typedef std::vector<modint>modvec;
private:
    modvec V;
public:
    class NTT
    {
    private:
        uint n;uint*T;modint*G;
    public:
        NTT():n(0),T(NULL),G(NULL){}
        NTT(uint len)
        {
            n=1;while(n<len)n<<=1;
            T=new uint[n],G=new modint[n],T[0]=0,G[0]=1;
            for(uint i=1;i<n;i++)T[i]=((i&1)?n|T[i>>1]:T[i>>1])>>1;
            modint w=power(g,(p-1)/n,p),*End=G+n;for(modint*_G=G+1;_G<End;_G++)*_G=_G[-1]*w;
        }
        ~NTT(){if(T)delete[]T,delete[]G,T=NULL,G=NULL;}
        inline uint size(){return n;}
        voi bzr(uint len)
        {
            if(T)delete[]T,delete[]G,T=NULL,G=NULL;
            n=1;while(n<len)n<<=1;
            T=new uint[n],G=new modint[n],T[0]=0,G[0]=1;
            for(uint i=1;i<n;i++)T[i]=((i&1)?n|T[i>>1]:T[i>>1])>>1;
            modint w=power(g,(p-1)/n,p),*End=G+n;for(modint*_G=G+1;_G<End;_G++)*_G=_G[-1]*w;
        }
        voi ntt(modvec&x,bol op)
        {
            if(x.size()<n)x.resize(n);
            for(uint i=0;i<n;i++)if(T[i]<i)std::swap(x[i],x[T[i]]);
            for(uint i=1,d=n>>1;d;i<<=1,d>>=1)for(uint j=0;j<n;j+=i<<1)
            {
                modint*w=G,t;for(uint k=0;k<i;k++,w+=d)x[i|j|k]=x[j|k]-(t=x[i|j|k]*(*w)),x[j|k]+=t;
            }
            if(op)
            {
                for(uint i=1;i*2<n;i++)std::swap(x[i],x[n-i]);
                modint t=modint(n).inv();for(uint i=0;i<n;i++)x[i]*=t;
            }
        }
        inline modint omega(uint t){return G[t%n];}
        NTT&operator=(NTT b)
        {
            if(T)delete[]T,delete[]G,T=NULL,G=NULL;
            if(!b.T)return*this;
            T=new uint[n],G=new modint[n=b.n];
            for(uint i=0;i<n;i++)T[i]=b.T[i],G[i]=b.G[i];
            return*this;
        }
    };
    class DIFDIT
    {
    private:
        uint n;modint*G;
    public:
        DIFDIT():n(0),G(NULL){}
        DIFDIT(uint len)
        {
            n=1;while(n<len)n<<=1;
            G=new modint[n],G[0]=1;
            modint w=power(g,(p-1)/n,p),*End=G+n;
            for(modint*_G=G+1;_G<End;_G++)*_G=_G[-1]*w;
        }
        ~DIFDIT(){if(G)delete[]G,G=NULL;}
        inline uint size(){return n;}
        voi bzr(uint len)
        {
            if(G)delete[]G;
            n=1;while(n<len)n<<=1;
            G=new modint[n],G[0]=1;
            modint w=power(g,(p-1)/n,p),*End=G+n;
            for(modint*_G=G+1;_G<End;_G++)*_G=_G[-1]*w;
        }
        voi dif(modvec&x)
        {
            if(x.size()<n)x.resize(n);
            for(uint i=n>>1,d=1;i;i>>=1,d<<=1)for(uint j=0;j<n;j+=i<<1) 
            {
                modint*w=G,u,t;for(uint k=0;k<i;k++,w+=d)x[j|k]=(u=x[j|k])+(t=x[i|j|k]),x[i|j|k]=(u-t)*(*w);
            }
        }
        voi dit(modvec&x)
        {
            if(x.size()<n)x.resize(n);
            for(uint i=1,d=n>>1;d;i<<=1,d>>=1)for(uint j=0;j<n;j+=i<<1)
            {
                modint*w=G,t;for(uint k=0;k<i;k++,w+=d)x[i|j|k]=x[j|k]-(t=x[i|j|k]*(*w)),x[j|k]+=t;
            }
            for(uint i=1;i*2<n;i++)std::swap(x[i],x[n-i]);
            modint t=modint(n).inv();for(uint i=0;i<n;i++)x[i]*=t;
        } 
        DIFDIT&operator=(DIFDIT b)
        {
            if(G!=NULL)delete[]G,G=NULL;
            if(b.G==NULL)return*this;
            G=new modint[n=b.n];
            for(uint i=0;i<n;i++)G[i]=b.G[i];
            return*this;
        }
    };
    poly_NTT(){}
    poly_NTT(uint n){V.resize(n);}
    poly_NTT(modvec V):V(V){}
    inline voi bzr(){V.clear();}
    inline voi push(modint v){V.push_back(v);}
    inline voi pop(){V.pop_back();}
    inline voi pop0s(){while(V.size()&&V.back().empty())V.pop_back();}
    inline voi chg_siz(uint n){V.resize(n);}
    inline voi chg_deg(uint n){V.resize(n+1);}
    inline bol empty(){return pop0s(),V.empty();}
    inline uint size(){return V.size();}
    inline uint deg(){return V.size()-1;}
    inline modint val(uint n){return n<size()?V[n]:modint();}
    inline modint&operator[](uint n){return V[n];}
    inline modvec GET(){return V;}
    inline decltype(V.begin()) begin(){return V.begin();}
    inline decltype(V.begin()) end(){return V.end();}
    poly_NTT reverse()
    {
        uint n=size();poly_NTT ans(n);
        for(uint i=0;i<n;i++)ans[i]=V[n-i-1];
        return ans;
    }
    friend poly_NTT operator+(poly_NTT a,poly_NTT b)
    {
        if(a.size()<b.size())a.chg_siz(b.size());
        for(uint i=0;i<b.size();i++)a[i]+=b[i];
        return a;
    }
    poly_NTT&operator+=(poly_NTT b)
    {
        if(size()<b.size())chg_siz(b.size());
        for(uint i=0;i<b.size();i++)V[i]+=b[i];
        return*this;
    }
    friend poly_NTT operator+(poly_NTT a,modint v)
    {
        if(!a.size())return{v};
        a[0]+=v;return a;
    }
    inline poly_NTT&operator+=(modint v)
    {
        if(!size())*this={v};else V[0]+=v;
        return*this;
    }
    friend poly_NTT operator+(modint v,poly_NTT a)
    {
        if(!a.size())return{v};
        a[0]+=v;return a;
    }
    friend poly_NTT operator-(poly_NTT a)
    {
        for(auto&s:a)s=-s;
        return a;
    }
    friend poly_NTT operator-(poly_NTT a,poly_NTT b)
    {
        if(a.size()<b.size())a.chg_siz(b.size());
        for(uint i=0;i<b.size();i++)a[i]-=b[i];
        return a;
    }
    poly_NTT&operator-=(poly_NTT b)
    {
        if(size()<b.size())chg_siz(b.size());
        for(uint i=0;i<b.size();i++)V[i]-=b[i];
        return*this;
    }
    friend poly_NTT operator-(poly_NTT a,modint v)
    {
        if(!a.size())return-v;
        a[0]-=v;return a;
    }
    inline poly_NTT&operator-=(modint v)
    {
        if(!size())*this={-v};else V[0]-=v;
        return*this;
    }
    friend poly_NTT operator-(modint v,poly_NTT a){return-a+v;}
    friend poly_NTT operator*(poly_NTT a,poly_NTT b)
    {
        a.pop0s(),b.pop0s();if(!a.size()||!b.size())return{};
        if(a.size()<=8||b.size()<=8)
        {
            modvec ans(a.size()+b.size()-1);
            for(uint i=0;i<a.size();i++)for(uint j=0;j<b.size();j++)ans[i+j]+=a[i]*b[j];
            return ans;
        }
        modvec&A=a.V,&B=b.V;DIFDIT s(A.size()+B.size()-1);
        s.dif(A),s.dif(B);for(uint i=0;i<s.size();i++)A[i]*=B[i];
        s.dit(A),a.pop0s();return a;
    }
    poly_NTT&operator*=(poly_NTT b){return*this=*this*b;}
    friend poly_NTT operator*(poly_NTT a,modint v)
    {
        for(auto&s:a)s*=v;
        return a;
    }
    poly_NTT&operator*=(modint v)
    {
        for(auto&t:V)t*=v;
        return*this;
    }
    friend poly_NTT operator*(modint v,poly_NTT a)
    {
        for(auto&s:a)s*=v;
        return a;
    }
    friend poly_NTT operator<<(poly_NTT a,uint k){modvec t(k);a.V.insert(a.begin(),t.begin(),t.end());return a;}
    inline poly_NTT&operator<<=(uint k){modvec t(k);return V.insert(begin(),t.begin(),t.end()),*this;}
    friend poly_NTT operator>>(poly_NTT a,uint k)
    {
        if(a.size()<=k)return{};
        return a.V.erase(a.begin(),a.begin()+k),a;
    }
    inline poly_NTT&operator>>=(uint k)
    {
        if(size()<=k)return*this={};
        return V.erase(begin(),begin()+k),*this;
    }
    friend poly_NTT sub_mul(poly_NTT a,poly_NTT b)
    {
        a.pop0s(),b.pop0s();if(!a.size()||!b.size())return{};
        uint len=(a=a.reverse()).size();if(b.size()>len)b.chg_siz(len);
        modvec&A=a.V,&B=b.V;DIFDIT s(len+B.size()-1);
        s.dif(A),s.dif(B);for(uint i=0;i<s.size();i++)A[i]*=B[i];
        s.dit(A),a.chg_siz(len),a=a.reverse();return a;
    }
    poly_NTT inv(){return inv(size());}
    poly_NTT inv(uint prec)
    {
        if(val(0).empty())return{};
        modvec ans;DIFDIT s;ans.push_back(V[0]==1?1:V[0].inv());
        for(uint tp=1;tp<prec;tp<<=1)
        {
            modvec f(tp<<1),t=ans;for(uint i=0;i<(tp<<1);i++)f[i]=val(i);
            s.bzr(tp<<1),s.dif(f),s.dif(t);for(uint i=0;i<(tp<<1);i++)f[i]*=-t[i];
            s.dit(f);for(uint i=0;i<tp;i++)f[i]=0;
            s.dif(f);for(uint i=0;i<(tp<<1);i++)f[i]*=t[i];
            s.dit(f),ans.resize(tp<<1);for(uint i=0;i<tp;i++)ans[i+tp]=f[i+tp];
        }
        ans.resize(prec);return ans;
    }
    poly_NTT sqrt(){return sqrt(size());}
    poly_NTT sqrt(uint prec)
    {
        if(val(0).empty())return{};
        modvec ans{V[0]==1?1:V[0].sqrt()};
        modvec invans{ans[0]==1?1:ans[0].inv()};
        modint w=modint(2).inv();DIFDIT s;
        for(uint tp=1;tp<prec;tp<<=1)
        {
            s.bzr(tp<<1);
            modvec r=invans,f(tp<<1),h(tp),t(tp<<1);
            s.dif(r);for(uint i=0;i<tp;i++)f[i]=ans[i];
            s.dif(f);for(uint i=0;i<(tp<<1);i++)f[i]*=-r[i];
            s.dit(f);for(uint i=0;i<tp;i++)f[i]=0;
            s.dif(f);for(uint i=0;i<(tp<<1);i++)f[i]*=r[i];
            s.dit(f);for(uint i=0;i<tp;i++)t[i+tp]=f[i+tp];
            s.dif(t);for(uint i=0;i<(tp<<1);i++)f[i]=val(i);
            s.dif(f);for(uint i=0;i<tp;i++)h[i]=val(i);
            s.dif(h);for(uint i=0;i<(tp<<1);i++)f[i]=f[i]*r[i]+h[i]*t[i];
            s.dit(f),ans.resize(tp<<1);for(uint i=tp;i<tp*2;i++)ans[i]=f[i]*w;
            if(tp*2<prec)
            {
                for(uint i=0;i<(tp<<1);i++)f[i]=ans[i];
                s.dif(f);for(uint i=0;i<(tp<<1);i++)f[i]*=-r[i];
                s.dit(f);for(uint i=0;i<tp;i++)f[i]=0;
                s.dif(f);for(uint i=0;i<(tp<<1);i++)f[i]*=r[i];
                s.dit(f),invans.resize(tp<<1);for(uint i=0;i<tp;i++)invans[i+tp]=f[i+tp];
            }
        }
        ans.resize(prec);return ans;
    }
    poly_NTT diff()
    {
        uint n=size();if(!n)return{};
        poly_NTT ans(n);for(uint i=1;i<n;i++)ans[i-1]=i*V[i];
        return ans;
    }
    poly_NTT inte()
    {
        uint n=size();if(!n)return modvec{0};
        poly_NTT ans(n+1);ans[1]=1;for(uint i=1;i<n;i++)ans[i+1]=ans[i]*i;
        modint v=(ans[n]*n).inv();for(uint i=n;i;i--)ans[i]*=V[i-1]*v,v*=i;
        return ans;
    }
    poly_NTT ln(){return ln(size());}
    poly_NTT ln(uint prec)
    {
        if(val(0)!=1)return{};
        poly_NTT a=diff();a.chg_siz(prec),(a*=inv(prec)).chg_siz(prec),a=a.inte(),a.chg_siz(prec);
        return a;
    }
    poly_NTT exp(){return exp(size());}
    poly_NTT exp(uint prec)
    {
        if(!val(0).empty())return{};
        modvec ans{1},invans{1};DIFDIT s;
        for(uint tp=1;tp<prec;tp<<=1)
        {
            s.bzr(tp<<1);
            modvec r=invans,f(tp<<1),h(tp<<1),t(tp<<1);
            s.dif(r);for(uint i=0;i<tp;i++)t[i]=ans[i];
            s.dif(t);for(uint i=0;i<(tp<<1);i++)f[i]=-t[i]*r[i];
            s.dit(f);for(uint i=0;i<tp;i++)f[i]=0;
            s.dif(f);for(uint i=0;i<(tp<<1);i++)f[i]*=r[i];
            s.dit(f);for(uint i=0;i<tp;i++)h[i+tp]=f[i+tp];
            s.dif(h);for(uint i=0;i<(tp<<1);i++)f[i]=0;
            for(uint i=1;i<tp;i++)f[i-1]=i*ans[i];
            s.dif(f);for(uint i=0;i<(tp<<1);i++)f[i]*=r[i]+h[i];
            s.dit(f),(f=poly_NTT(f).inte().GET()).resize(tp<<1);
            for(uint i=0;i<tp;i++)f[i]=0,f[i+tp]=val(i+tp)-f[i+tp];
            s.dif(f);for(uint i=0;i<(tp<<1);i++)f[i]*=t[i];
            s.dit(f),ans.resize(tp<<1);for(uint i=tp;i<(tp<<1);i++)ans[i]=f[i];
            if(tp*2<prec)
            {
                for(uint i=0;i<(tp<<1);i++)f[i]=ans[i];
                s.dif(f);for(uint i=0;i<(tp<<1);i++)f[i]*=-r[i];
                s.dit(f);for(uint i=0;i<tp;i++)f[i]=0;
                s.dif(f);for(uint i=0;i<(tp<<1);i++)f[i]*=r[i];
                s.dit(f),invans.resize(tp<<1);for(uint i=0;i<tp;i++)invans[i+tp]=f[i+tp];
            }
        }
        ans.resize(prec);return ans;
    }
    friend poly_NTT operator/(poly_NTT a,poly_NTT b)
    {
        a.pop0s(),b.pop0s();if(a.size()<b.size())return{};
        poly_NTT ans=a.reverse()*b.reverse().inv(a.size()-b.size()+1);
        ans.chg_siz(a.size()-b.size()+1);return ans.reverse();
    }
    poly_NTT&operator/=(poly_NTT b){return*this=*this/b;}
    friend poly_NTT operator%(poly_NTT a,poly_NTT b){return a-a/b*b;}
    poly_NTT&operator%=(poly_NTT b){return*this=*this%b;}
};
template<const ullt p,const ullt g>
class poly_eval
{
public:
    typedef ConstMod::mod_ullt<p>modint;
    typedef std::vector<modint>modvec;
    typedef poly_NTT<p,g>poly;
private:
    std::vector<poly>G,User;modvec X;
    voi dfs1(uint u,uint l,uint r)
    {
        if(r-l<=128)
        {
            poly&P=G[u];P.chg_siz(r-l+1);P[0]=1;
            for(uint i=0;i<r-l;i++)for(uint j=i;~j;j--)P[j+1]-=P[j]*X[i+l];
            return;
        }
        uint mid=(l+r)/2;dfs1(u<<1,l,mid),dfs1(u<<1|1,mid,r),G[u]=G[u<<1]*G[u<<1|1];
    }
    voi dfs2(uint u,uint l,uint r)
    {
        User.back().chg_siz(r-l);
        if(r-l<=128)
        {
            std::vector<modvec>P(r-l+1,modvec(r-l+1));P[0][0]=1;
            for(uint i=0;i<r-l;i++)for(uint j=i;~j;j--)P[i+1][j+1]-=P[i][j]*X[i+l],P[i+1][j]=P[i][j];
            modvec A=User.back().GET();
            for(uint i=r-l-1;~i;i--)
            {
                modint w;
                for(uint j=0;j<=i;j++)w+=P[i][j]*A[j];
                for(uint j=1;j<=i;j++)A[j-1]-=A[j]*X[i+l];
                X[i+l]=w;
            }
            return;
        }
        uint mid=(l+r)/2;
        User.push_back(sub_mul(User.back(),G[u<<1|1])),dfs2(u<<1,l,mid);
        User.back()=sub_mul(User[User.size()-2],G[u<<1]),dfs2(u<<1|1,mid,r);
        User.pop_back();
    }
public:
    voi operator()(poly P,modvec&Q)
    {
        if(P.size()<=128||Q.size()<=128)
        {
            for(auto&x:Q)
            {
                modint ans,v(1);
                for(auto&a:P)ans+=a*v,v*=x;
                x=ans;
            }
            return;
        }
        uint m=1;while(m*128<Q.size())m<<=1;
        G.resize(m<<1),User.clear(),X=Q,dfs1(1,0,Q.size());
        User.push_back(sub_mul(P,G[1].inv(std::max<uint>(P.size(),X.size())+1)));
        dfs2(1,0,Q.size()),G.clear(),User.clear(),Q=X,X.clear();
    }
};
template<const ullt p,const ullt g>
class poly_inter
{
public:
    typedef ConstMod::mod_ullt<p>modint;
    typedef std::vector<modint>modvec;
    typedef poly_NTT<p,g>poly;
    typedef poly_eval<p,g>eval;
private:
    std::vector<poly>F,G;modvec A,B;
    voi dfs1(uint u,uint l,uint r)
    {
        if(r-l<=128)
        {
            poly&P=G[u];P.chg_siz(r-l+1),P[0]=1;
            for(uint i=0;i<r-l;i++)for(uint j=i;~j;j--)P[j+1]+=P[j],P[j]*=-A[i+l];
            return;
        }
        dfs1(u<<1,l,(l+r)>>1),dfs1(u<<1|1,(l+r)>>1,r);
        G[u]=G[u<<1]*G[u<<1|1];
    }
    voi dfs2(uint u,uint l,uint r)
    {
        if(r-l<=128)
        {
            poly&P=F[u];modvec Q(r-l+1);P.chg_siz(r-l),Q[0]=1;
            for(uint i=0;i<r-l;i++)
            {
                for(uint j=i;~j;j--)P[j+1]+=P[j],P[j]*=-A[i+l];
                for(uint j=i;~j;j--)P[j]+=Q[j]*B[i+l],Q[j+1]+=Q[j],Q[j]*=-A[i+l];
            }
            return;
        }
        dfs2(u<<1,l,(l+r)>>1),dfs2(u<<1|1,(l+r)>>1,r);
        F[u]=F[u<<1]*G[u<<1|1]+G[u<<1]*F[u<<1|1];
    }
public:
    poly operator()(modvec X,modvec Y)
    {
        uint n=std::min(X.size(),Y.size());if(!n)return poly();
        X.resize(n),Y.resize(n);
        uint m=1;while(m*128<n)m<<=1;
        F.resize(m<<1),G.resize(m<<1),A=X,dfs1(1,0,n);
        eval()(G[1].diff(),B=A);for(uint i=0;i<n;i++)B[i]=Y[i]/B[i];
        dfs2(1,0,n);
        poly ans=F[1];
        F.clear(),G.clear(),A.clear(),B.clear();
        return ans;
    }
};
template<const ullt p,const ullt g>
class poly_cpd
{
public:
    typedef ConstMod::mod_ullt<p>modint;
    typedef std::vector<modint>modvec;
    typedef poly_NTT<p,g>poly;
    modvec Turn(std::vector<llt>A)
    {
        uint n=A.size();
        modvec ans(n);
        for(uint i=0;i<n;i++)ans.push_back((A[i]%(llt)p+p)%p);
        return ans;
    }
    modint p_eval(poly P,modint x)
    {
        modint ans;
        for(uint i=P.deg();~i;i--)ans=ans*x+P[i];
        return ans;
    }
    poly z_npow(poly P,uint n)
    {
        if(P.empty())return P;
        poly ans(P.deg()*n+1);
        for(uint i=0;i<P.size();i++)ans[i*n]+=P[i];
        return ans;
    }
    poly z_npow(poly P,uint n,uint prec)
    {
        poly ans(prec);
        for(uint i=0;i<P.size()&&i*n<prec;i++)ans[i*n]+=P[i];
        return ans;
    }
    poly z_mul_k(poly P,modint k)
    {
        modint t(1);
        for(uint i=0;i<P.size();i++)P[i]*=t,t*=k;
        return P;
    }
    poly z_add_v(poly P,modint v)
    {
        uint n=P.size();if(!n)return P;
        modvec A(n),B(n);
        A[0]=1;for(uint i=1;i<n;i++)A[i]=A[i-1]*i;
        B[n-1]=A[n-1].inv();for(uint i=n-1;i;i--)B[i-1]=B[i]*i;
        poly User(n);modint w(1);
        for(uint i=0;i<n;i++)P[i]*=A[i],User[i]=w*B[i],w*=v;
        P=sub_mul(P,User),P.chg_siz(n);
        for(uint i=0;i<n;i++)P[i]*=B[i];
        return P;
    }
    poly PolyaInv(poly P){return PolyaInv(P,P.size());}
    poly PolyaInv(poly P,uint prec){return(modint(1)-P).inv(prec);}
    poly PolyaExp(poly P){return PolyaExp(P,P.size());}
    poly PolyaExp(poly P,uint prec)
    {
        modvec A(prec);A[0]=1;for(uint i=1;i<prec;i++)A[i]=A[i-1]*i;
        modint v=A[prec-1].inv();for(uint i=prec-1;i;i--)A[i]=A[i-1]*v,v*=i;
        poly ans(prec);
        for(uint i=1;i<prec;i++)for(uint j=1;i*j<prec&&j<P.size();j++)ans[i*j]+=P[j]*A[i];
        return ans.exp(prec);
    }
    poly PolyaExpMdf(poly P){return PolyaExpMdf(P,P.size());}
    poly PolyaExpMdf(poly P,uint prec)
    {
        modvec A(prec);A[0]=1;for(uint i=1;i<prec;i++)A[i]=A[i-1]*i;
        modint v=A[prec-1].inv();for(uint i=prec-1;i;i--)A[i]=A[i-1]*v,v*=i;
        for(uint i=2;i<prec;i+=2)A[i]=-A[i];
        poly ans(prec);
        for(uint i=1;i<prec;i++)for(uint j=1;i*j<prec&&j<P.size();j++)ans[i*j]+=P[j]*A[i];
        return ans.exp(prec);
    }
    voi println(modvec P){println(poly(P),P.size());}
    voi println(modvec P,uint n){println(poly(P),n);}
    voi println(poly P){println(P,P.size());}
    voi println(poly P,uint n)
    {
        for(uint i=0;i<n;i++)P.val(i).print(" \n"[i==n-1]);
        if(!n)putchar('\n');
    }
};
template<const ullt p,const ullt g>
class poly_nums
{
public:
    typedef ConstMod::mod_ullt<p>modint;
    typedef std::vector<modint>modvec;
    typedef poly_NTT<p,g>poly;
    typedef poly_cpd<p,g>cpd;
    modvec S2R(uint n)
    {
        if(!n)return{1};
        modint v=1;for(uint i=1;i<=n;i++)v*=i;;
        modvec A(n+1),Q(n+1);A[1]=1,Q[n]=v.inv();for(uint i=n;i;i--)Q[i-1]=Q[i]*i;
        std::vector<uint>Prime;
        std::vector<bol>G(n+1);
        for(uint i=2,lim;i<=n;i++)
        {
            lim=n/i;
            if(!G[i])
            {
                Prime.push_back(i),A[i]=modint(i)^n;
                for(uint j=i;j<=lim;j*=i)A[i*j]=A[i]*A[j],G[i*j]=true;
            }
            for(auto w:Prime)if(w<=lim&&i%w)
                for(uint j=w;j<=lim;j*=w)A[i*j]=A[i]*A[j],G[i*j]=true;
            else break;
        }
        for(uint i=0;i<=n;i++)A[i]*=Q[i];
        for(uint i=1;i<=n;i+=2)Q[i]=-Q[i];
        A=(poly(A)*Q).GET(),A.resize(n+1);
        return A;
    }
    modvec S2C(uint n,uint prec)
    {
        if(n>=prec)return modvec(prec);
        prec-=n;
        modvec Q(prec);
        modint v(1);for(uint i=1;i<=prec;i++)v*=i;
        v=v.inv();for(uint i=prec;i;i--)Q[i-1]=v,v*=i;
        modvec ans=(poly(Q).ln(prec)*modint(n)).exp(prec).GET();
        for(uint i=0;i<prec;i++)ans[i]*=v,v*=n+i+1;
        Q=modvec(n),ans.insert(ans.begin(),Q.begin(),Q.end());
        return ans;
    }
    modvec S1R(uint n)
    {
        if(!n)return{1};
        if(n&1)
        {
            modvec F=S1R(n-1);F.insert(F.begin(),modint());
            for(uint i=0;i<n;i++)F[i]+=(n-1)*F[i+1];
            return F;
        }
        modvec F=S1R(n>>1);return(F*cpd().z_add_v(F,n>>1)).GET();
    }
    modvec S1C(uint n,uint prec)
    {
        if(n>=prec)return modvec(prec);
        prec-=n;
        modvec Q(prec);
        modint v(1);for(uint i=1;i<=prec;i++)v*=i;
        v=v.inv();for(uint i=prec;i;i--)Q[i-1]=v,v*=i;
        for(uint i=1;i<=prec;i++)Q[i-1]*=v,v*=i;
        modvec ans=(poly(Q).ln(prec)*modint(n)).exp(prec).GET();
        v=1;for(uint i=0;i<prec;i++)ans[i]*=v,v*=n+i+1;
        Q=modvec(n),ans.insert(ans.begin(),Q.begin(),Q.end());
        return ans;
    }
    modvec PowSum(uint n,modint m)
    {
        modvec A(n),B(n);modint v(1);
        for(uint i=1;i<=n+1;i++)v*=i;
        v=v.inv();for(uint i=n+1;i;i--)A[i-1]=v,v*=i;
        for(uint i=0;i<n;i++)B[i]=(v*=m)*A[i];
        B=(B*poly(A).inv()).GET(),B.resize(n),v=1;
        for(uint i=0;i<n;v*=++i)B[i]*=v;
        return B;
    }
};
}
// Your shadow Gets in the way of my light
const ullt Mod=998244353,g=3;
typedef ConstMod::mod_ullt<Mod>modint;
typedef std::vector<modint>modvec;
typedef NTT_POLY::poly_NTT<Mod,g>poly;
typedef NTT_POLY::poly_eval<Mod,g>eval;
typedef NTT_POLY::poly_inter<Mod,g>inter;
typedef NTT_POLY::poly_cpd<Mod,g>cpd;
typedef NTT_POLY::poly_nums<Mod,g>nums;
modint P[500005],Q[500005];
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#endif
    uint n,m,k;scanf("%u%u%u",&n,&m,&k);
    P[0]=1;for(uint i=1;i<=n*m;i++)P[i]=P[i-1]*i;
    Q[n*m]=P[n*m].inv();for(uint i=n*m;i;i--)Q[i-1]=Q[i]*i;
    poly A(n*m+1),B(k+1);
    for(uint i=0;i<=k;i++)B[i]=Q[i]*Q[k-i]*(i&1?-modint(1):1);
    for(uint i=k;i<=n*m;i++)A[i]=Q[n*m-i]*Q[i-k];
    A=sub_mul(A,B);
    for(uint i=0;i<A.size();i++)A[i]*=P[i]*P[n*m-i];
    modint ans;
    for(uint j=0;j<=m;j++)for(uint t=0;t<=n;t++)
        ans+=P[m]*Q[j]*Q[m-j]*P[n]*Q[t]*Q[n-t]*((m+j+t)&1?-modint(1):1)*A.val((m-j)*t+j*(n-t));
    ans/=modint(2)^(n+m);
    ans.println();
    return 0;
}

// 那就是希望。
// 即便需要取模，也是光明。