#include using namespace std; using ll=long long; //#define int ll #define rng(i,a,b) for(int i=int(a);i; template using vc=vector; template using vvc=vc>; #define pb push_back #define eb emplace_back #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int((x).size()) using vi=vc; template void chmin(t&a,const t&b){if(a>b)a=b;} using uint=unsigned; using ull=unsigned long long; struct modinfo{uint mod,root;}; template struct modular{ static constexpr uint const&mod=ref.mod; static modular root(){return modular(ref.root);} uint v; modular(ll vv=0){s(vv%mod+mod);} modular&s(uint vv){ v=vv>=1; } return res; } modular inv()const{return pow(mod-2);} }; //size of input must be a power of 2 //output of forward fmt is bit-reversed //output elements are in the range [0,mod*4) //input of inverse fmt should be bit-reversed template void inplace_fmt(const int n,mint*const f,bool inv){ static constexpr uint mod=mint::mod; static constexpr uint mod2=mod*2; static const int L=30; static mint g[L],ig[L],p2[L]; if(g[0].v==0){ rep(i,L){ mint w=-mint::root().pow(((mod-1)>>(i+2))*3); g[i]=w; ig[i]=w.inv(); p2[i]=mint(1<>=1){//input:[0,mod) rep(i,b){ uint x=f[i+b].v; f[i+b].v=f[i].v+mod-x; f[i].v+=x; } } if(b>>=1){//input:[0,mod*2) mint p=1; for(int i=0,k=0;i>=1){//input:[0,mod*3) mint p=1; for(int i=0,k=0;i>=1){//input:[0,mod*4) mint p=1; for(int i=0,k=0;i void inplace_fmt(vector&f,bool inv){ inplace_fmt(si(f),f.data(),inv); } template void half_fmt(const int n,mint*const f){ static constexpr uint mod=mint::mod; static constexpr uint mod2=mod*2; static const int L=30; static mint g[L],h[L]; if(g[0].v==0){ rep(i,L){ g[i]=-mint::root().pow(((mod-1)>>(i+2))*3); h[i]=mint::root().pow((mod-1)>>(i+2)); } } int b=n; int lv=0; if(b>>=1){//input:[0,mod) mint p=h[lv++]; for(int i=0,k=0;i>=1){//input:[0,mod*2) mint p=h[lv++]; for(int i=0,k=0;i>=1){//input:[0,mod*3) mint p=h[lv++]; for(int i=0,k=0;i>=1){//input:[0,mod*4) mint p=h[lv++]; for(int i=0,k=0;i void half_fmt(vector&f){ half_fmt(si(f),f.data()); } template vc multiply(vc x,const vc&y,bool same=false){ int n=si(x)+si(y)-1; int s=1; while(s z(s); rep(i,si(y))z[i]=y[i]; inplace_fmt(z,false); rep(i,s)x[i]*=z[i]; }else{ rep(i,s)x[i]*=x[i]; } inplace_fmt(x,true);x.resize(n); return x; } constexpr modinfo base{998244353,3}; using mint=modular; const int vmax=1000010; mint fact[vmax],finv[vmax],invs[vmax]; void initfact(){ fact[0]=1; rng(i,1,vmax) fact[i]=fact[i-1]*i; finv[vmax-1]=fact[vmax-1].inv(); for(int i=vmax-2;i>=0;i--) finv[i]=finv[i+1]*(i+1); for(int i=vmax-1;i>=1;i--) invs[i]=finv[i]*fact[i-1]; } mint binom(int a,int b){ return fact[a+b]*finv[a]*finv[b]; } vc hori(vcx,int h){ int w=si(x)-1; vcy(w+1); rep(i,w+1)y[i]=binom(i,h); auto z=multiply(x,y); z.resize(w+1); return z; } vc vert(vcx,int h){ int w=si(x)-1; rep(i,w+1)x[i]*=finv[w-i]; vc y(fact,fact+(w+h+1)); auto z=multiply(x,y); vc res(h+1); rep(i,h+1)res[i]=z[w+i]*finv[i]; return res; } vc advance(vi a,int h,vc up){ { int cnt=0; rep(i,si(a))if(a[i]<0)cnt++;else break; a.erase(a.bg,a.bg+cnt); up.erase(up.bg,up.bg+cnt); } int n=si(a); assert(si(up)==n+1); if(n<=250||h<=250){ vc res(h+1); rep(i,h+1){ rep(j,n)if(a[j]>=i){ up[j+1]+=up[j]; } res[i]=up[n]; } return res; } int t=(n+h)/2; int x=0,y=0; while(x+y res(h+1); vc nx(n-x+1); { auto ue=hori(vc(x+all(up)),y); rep(i,n-x+1)nx[i]=ue[i]; } { auto migi=vert(vc(x+all(up)),y); rep(i,y+1)res[i]+=migi[i]; } if(x){ auto hidari=advance(vi(a.bg,a.bg+x-1),a[x-1],vc(up.bg,up.bg+x)); hidari.resize(y+1); { auto ue=vert(hidari,n-x); rep(i,n-x+1)nx[i]+=ue[i]; } { auto migi=hori(hidari,n-x); rep(i,y+1)res[i]+=migi[i]; } } if(y>s; int cnt=0; for(auto c:s){ if(c=='B'){ cnt++; } else{ a.push_back(cnt); } } int n=a.size(); if(n==0){ cout<<1< up(n+1); up[0]=1; auto ans=advance(a,a[n-1],up); cout<