#include #include #include #include #include #include #include #include #include #include #define mkp make_pair #define mkt make_tuple #define rep(i,n) for(int i = 0; i < (n); ++i) #define all(v) v.begin(),v.end() using namespace std; typedef long long ll; const ll MOD=998244353; template void chmin(T &a,const T &b){if(a>b) a=b;} template void chmax(T &a,const T &b){if(a0){ if(n&1) res=res*x%MOD; x=x*x%MOD; n>>=1; } return res; } ll mod_inverse(ll x){ return mod_pow(x,MOD-2); } void add(ll &a,ll b){ a=(a+b)%MOD; } void mul(ll &a,ll b){ a%=MOD;b%=MOD; a=a*b%MOD; } //const ll MOD=998244353; // MOD == 119*2^23+1 //depends on mod_pow,mod_inverse ll root[24],invroot[24]; void NTT_init(){ for(int i=0;i<24;++i){ root[i]=mod_pow(3,(MOD-1)/(1< NTT(vector a,bool inverse=false){ int n=a.size(); int high=0; for(int i=0;(1<>k&1) mask|=(1<<(high-1-k)); } if(i=MOD) a[k]-=MOD; a[k+m/2]=(s-t+MOD)%MOD; //while(a[k+m/2]>=MOD) a[k+m/2]-=MOD; powzeta=powzeta*zeta%MOD; } } } if(inverse){ ll invn=mod_inverse(n); for(int i=0;i convolute(vector A,vector B){ int size=A.size()+B.size()-1; int n=1; while(n>S; int N=S.size(); vector alp(26,0); rep(i,N) ++alp[S[i]-'a']; sort(all(alp)); setComb(); NTT_init(); vector ans={1}; for(int k=0;k<26;++k){ if(alp[k]==0) continue; vector A(alp[k]+1); for(int j=0;j<=alp[k];++j) A[j]=ifac[j]; ans=convolute(ans,A); } for(int i=0;i