#include using namespace std; #define modulo 998244353 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 1000000005 int beki(long long a,long long b,int M = modulo){ int x = 1; while(b!=0){ if(b&1){ x=((long long)x*a)%M; } a=((long long)a*a)%M; b>>=1; } return x; } int gyakugen(int a){ return beki(a,modulo-2); } struct combi{ deque kaijou; deque kaijou_; combi(int n){ kaijou.push_back(1); for(int i=1;i<=n;i++){ kaijou.push_back(mod(kaijou[i-1]*i)); } int b=gyakugen(kaijou[n]); kaijou_.push_front(b); for(int i=1;i<=n;i++){ int k=n+1-i; kaijou_.push_front(mod(kaijou_[0]*k)); } } int combination(int n,int r){ if(r>n)return 0; int a = mod(kaijou[n]*kaijou_[r]); a=mod(a*kaijou_[n-r]); return a; } int junretsu(int a,int b){ int x = mod(kaijou_[a]*kaijou_[b]); x=mod(x*kaijou[a+b]); return x; } int catalan(int n){ return mod(combination(2*n,n)*gyakugen(n+1)); } }; void NTT(vector &A){ int n = A.size(); vector tmp(n,0); int mask = n-1; for(int i=n>>1;i>=1;i>>=1){ int r = (modulo-1)/n; r *= i; int w = beki(3,r); int now = 1; for(int j=0;j>i)&1){ num = i; break; } } if(num&1){ swap(A,tmp); for(int i=0;i do_NTT(vector A,vector B){ int n = A.size()+B.size()-1; if(min(A.size(),B.size())<=150){ vector ret(n,0); for(int i=0;i=n){ n = (1< c(n); for(int i=0;i cnt(26,0); string S; cin>>S; for(int i=0;i> now; for(int i=0;i<26;i++){ if(cnt[i]==0)continue; vector x(cnt[i]+1,1); now.push_back(x); } while(now.size()!=1){ vector> New; for(int i=0;i X = do_NTT(now[i],now[i+1]); for(int j=0;j0&&X.back()==0)X.pop_back(); New.push_back(X); } swap(now,New); } int ans =0; for(int i=1;i