#include using i64=long long int; using u64=unsigned long long int; using namespace std; template struct modint{ u64 val; modint(i64 val_=0):val((val_%i64(mod)+i64(mod))%i64(mod)){} modint operator-(){ return (val==0)?0:mod-val; } modint operator+(modint rhs){ return modint(*this)+=rhs; } modint operator-(modint rhs){ return modint(*this)-=rhs; } modint operator*(modint rhs){ return modint(*this)*=rhs; } modint operator/(modint rhs){ return modint(*this)/=rhs; } modint pow(i64 rhs){ modint res=1,now=(*this); while(rhs){ res*=((rhs&1)?now:1),now*=now,rhs>>=1; } return res; } modint &operator+=(modint rhs){ val+=rhs.val,val-=((val>=mod)?mod:0); return (*this); } modint &operator-=(modint rhs){ val+=((val>(std::istream& is,modint& x){ u64 t; is>>t,x=t; return is; } }; template struct comb{ vector dat,idat; comb(int mx=3000000):dat(mx+1,1),idat(mx+1,1){ for(int i=1;i<=mx;++i){ dat[i]=dat[i-1]*i; } idat[mx]/=dat[mx]; for(int i=mx;i>0;--i){ idat[i-1]=idat[i]*i; } } T operator()(int n,int k){ if(n==k){ return 1; } if(n<0||k<0||n struct NTT{ typedef modint mint; mint g; vector rev; NTT(){ for(g=2;;g+=1){ if(g.pow((mod-1)>>1)!=1){ return; } } } void dft(vector& f){ int siz=f.size(); for(int i=0;i operator()(vector a,vector b){ int cnt=0,siz=1,mxsiz=a.size()+b.size()-1; while(siz>1]>>1)+(1<<(cnt-1))*(i&1); } a.resize(siz),b.resize(siz),dft(a),dft(b); for(int i=0;i mint; string S; int A,B,C; cin>>S>>A>>B>>C; int N=S.size(); int P=count(S.begin(),S.end(),'a'),Q=count(S.begin(),S.end(),'b'),R=count(S.begin(),S.end(),'c'); int T=A-P,U=B-Q,V=C-R; comb Cb; NTT ntt; vector tmp(T+U+1); for(int i=0;i<=T+U;++i){ tmp[i]=Cb(R-1+i,R-1)*Cb(V+P+Q+(T+U-i),P+Q+(T+U-i)); if(0 f(T+1),g(U+1); for(int i=0;i<=T;++i){ f[i]=Cb.idat[i]*Cb(T-i+Q-1,Q-1); } for(int j=0;j<=U;++j){ g[j]=Cb.idat[j]*Cb(U-j+P-1,P-1); } auto h=ntt(f,g); mint ans=0; for(int k=0;k<=T+U;++k){ ans+=tmp[k]*h[k]*Cb.dat[k]; } cout<