#include using namespace std; #if __has_include() #include #endif using ll=long long; using ull=unsigned long long; using P=pair; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateistream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} templateistream &operator>>(istream &is,tuple&a){is>>std::get<0>(a)>>std::get<1>(a)>>std::get<2>(a);return is;} templateistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define overload3(_1,_2,_3,name,...) name #define rep1(i,n) for(int i=0;i<(int)(n);i++) #define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++) #define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__) #define reps(i,l,r) rep2(i,l,r) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) #define fin(x) return cout<<(x)<<'\n',static_cast(0) #define yn(x) cout<<((x)?"Yes\n":"No\n") #define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end()) ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } #ifdef LOCAL #include #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) templateostream &operator<<(ostream &os,const pair&p){os<>testcase; for(int i=0;i #include template constexpr std::enable_if_t::digits<=32,int>msb(T n){return n==0?-1:31-__builtin_clz(n);} template constexpr std::enable_if_t<(std::numeric_limits::digits>32),int>msb(T n){return n==0?-1:63-__builtin_clzll(n);} template constexpr std::enable_if_t::digits<=32,int>lsb(T n){return n==0?-1:__builtin_ctz(n);} template constexpr std::enable_if_t<(std::numeric_limits::digits>32),int>lsb(T n){return n==0?-1:__builtin_ctzll(n);} template constexpr std::enable_if_t,T>floor_pow2(T n){return n==0?0:T(1)< constexpr std::enable_if_t,T>ceil_pow2(T n){return n<=1?1:T(1)<<(msb(n-1)+1);} constexpr unsigned long long binary_gcd(unsigned long long a,unsigned long long b){ if(a==0||b==0||a==b)return ab)a=(a-b)>>lsb(a-b); else b=(b-a)>>lsb(b-a); } return a<<(n>64); u32 r=x-y*m; return m<=r?y-1:y; } inline u32 rem(u64 x)const{ if(m==1)return 0; u64 y=u64((u128(x)*im)>>64); u32 r=x-y*m; return m<=r?r+m:r; } inline std::pairquo_rem(u64 x)const{ if(m==0)return std::make_pair(x,0); u64 y=u64((u128(x)*im)>>64); u32 r=x-y*m; return m<=r?std::make_pair(y-1,r+m):std::make_pair(y,r); } inline u32 pow(u32 a,u64 p)const{ u32 res=m!=1; while(p){ if(p&1)res=rem(u64(res)*a); a=rem(u64(a)*a); p>>=1; } return res; } }; namespace prime_impl{ constexpr int table_size=1<<16; bool table[table_size]; struct prime_table_init{ prime_table_init(){ table[0]=table[1]=true; for(int i=2;i>=1; for(unsigned long long base:{2,7,61}){ unsigned long long t=d; unsigned long long y=1; while(t>0){ if(t&1)y=br.rem(y*base); base=br.rem(base*base); t>>=1; } t=d; while(t!=n-1&&y!=1&&y!=n-1){ y=br.rem(y*y); t<<=1; } if(y!=n-1&&t%2==0)return false; } return true; } unsigned long long d=n-1; int s=0; while(!(d&1))d>>=1,s++; int q=63; while(!(d>>q))q--; unsigned long long r=n; for(int i=0;i<5;i++)r*=2-r*n; auto redc=[&r,&n](__uint128_t x)->unsigned long long { x=(x+__uint128_t((unsigned long long)x*-r)*n)>>64; return x>=n?x-n:x; }; __uint128_t r2=-__uint128_t(n)%n; unsigned long long one=redc(r2); for(unsigned long long base:{2,325,9375,28178,450775,9780504,1795265022}){ if(base%n==0)continue; unsigned long long a=base=redc((base%n)*r2); for(int i=q-1;i>=0;i--){ a=redc(__uint128_t(a)*a); if(d>>i&1)a=redc(__uint128_t(a)*base); } if(a==one)continue; for(int i=1;a!=n-one;i++){ if(i>=s)return false; a=redc(__uint128_t(a)*a); } } return true; } std::vectorfactorize(unsigned long long n)noexcept{ std::vectorret; auto div=[](unsigned long long x)noexcept->unsigned long long { unsigned long long r=x; for(int i=0;i<5;i++)r*=2-r*x; unsigned long long r2=-__uint128_t(x)%x; auto redc=[&r,&x](__uint128_t t)->unsigned long long { t=(t+__uint128_t((unsigned long long)t*-r)*x)>>64; return t>=x?t-x:t; }; unsigned long long a=0,b=0; const unsigned long long one=redc(r2); unsigned long long e=one; int m=1ll<<((63-__builtin_clzll(x))>>3); while(true){ unsigned long long ca=a,cb=b; unsigned long long sk=one; for(int i=0;id?c-d:d-c)); } unsigned long long g=binary_gcd(redc(sk),x); if(g>1){ if(gd?c-d:d-c,x); if(cg>1){ if(cg>=1; ret.push_back(2); } if(n==1)return ret; st[p++]=n; while(p){ unsigned long long now=st[--p]; if(isprime(now)){ ret.push_back(now); continue; } unsigned long long d=div(now); st[p++]=d; now/=d; if(now!=1)st[p++]=now; } return ret; } template std::enable_if_t,T>carmichael(T n){ auto f=factorize(n); std::sort(f.begin(),f.end()); T res=1; for(int l=0,r=0;l=3)res=T(1)<<(r-l-2); } else{ T prod=f[l]-1; for(int i=0;i=3)res=1<<(t-2); for(int i=3;i*i<=n;i++)if(n%i==0){ int c=0; while(n%i==0){ n/=i; c++; } int prod=i-1; for(int j=0;j struct mod_int{ private: static constexpr unsigned int umod=static_cast(m); static constexpr unsigned int car=carmichael_constexpr(m); using uint=unsigned int; using mint=mod_int; uint v; static_assert(mval()<=1)return *this; if constexpr(m%8==1){ mint b=2; while(b.pow((m-1)/2).val()==1)b++; int m2=m-1,e=0; while(m2%2==0)m2>>=1,e++; mint x=this->pow((m2-1)/2); mint y=(*this)*x*x; x*=*this; mint z=b.pow(m2); while(y.val()!=1){ int j=0; mint t=y; while(t.val()!=1)t*=t,j++; z=z.pow(1<<(e-j-1)); x*=z; z*=z; y*=z;e=j; } return x; } else if constexpr(m%8==5){ mint ret=this->pow((m+3)/8); if((ret*ret).val()==this->val())return ret; else return ret*mint::raw(2).pow((m-1)/4); } else{ return this->pow((m+1)/4); } } public: using value_type=uint; mod_int():v(0){} template,std::nullptr_t> =nullptr> mod_int(T a){ a%=m; if(a<0)v=a+umod; else v=a; } template,std::nullptr_t> =nullptr> mod_int(T a):v(a%umod){} static constexpr mint raw(int a){ mint ret; ret.v=a; return ret; } inline uint val()const{return this->v;} static constexpr int mod(){return m;} inline mint &operator+=(const mint &b){ this->v+=b.v; if(this->v>=umod)this->v-=umod; return *this; } inline mint &operator-=(const mint &b){ this->v-=b.v; if(this->v>=umod)this->v+=umod; return *this; } inline mint &operator*=(const mint &b){ this->v=((unsigned long long)this->v*b.v)%umod; return *this; } inline mint &operator/=(const mint &b){ *this*=b.inv(); return *this; } inline mint operator+()const{return *this;} inline mint operator-()const{return mint()-*this;} friend inline mint operator+(const mint &a,const mint &b){return mint(a)+=b;} friend inline mint operator-(const mint &a,const mint &b){return mint(a)-=b;} friend inline mint operator*(const mint &a,const mint &b){return mint(a)*=b;} friend inline mint operator/(const mint &a,const mint &b){return mint(a)/=b;} friend inline bool operator==(const mint &a,const mint &b){return a.val()==b.val();} friend inline bool operator!=(const mint &a,const mint &b){return !(a==b);} inline mint operator++(int){ mint ret=*this; *this+=1; return ret; } inline mint operator--(int){ mint ret=*this; *this-=1; return ret; } mint pow(long long n)const{ mint ret=mint::raw(1),a(*this); while(n){ if(n&1)ret*=a; a*=a; n>>=1; } return ret; } inline mint inv()const{ assert(this->v!=0); return pow(car-1); } std::optionalsqrt()const{ if(this->val()<=1||this->pow((m-1)/2)==1)return std::make_optional(this->sqrt_impl()); else return std::nullopt; } static constexpr unsigned int order(){return car;} friend std::istream &operator>>(std::istream &is,mint &b){ long long a; is>>a; b=mint(a); return is; } friend std::ostream &operator<<(std::ostream &os,const mint &b){ os< struct std::hash>{ std::size_t operator()(mod_intx)const{ return std::hash()(x.val()); } }; using mint998=mod_int<998244353>; using mint107=mod_int<1000000007>; using mint=mint998; void SOLVE(){ int n,m; string s; cin>>n>>m>>s; mint ans=0; vector>g(n); rep(i,m){ int u,v; cin>>u>>v; u--,v--; g[u].push_back(v); g[v].push_back(u); } string aoi="aoi?"; int q=count(all(s),'?'); rep(i,n){ if(s[i]!='?'&&s[i]!='o')continue; int cnt[4]={0,0,0,0}; for(int j:g[i]){ rep(k,4)if(s[j]==aoi[k])cnt[k]++; } int fr=q-(s[i]=='?'); ans+=mint(cnt[0])*cnt[2]*mint(26).pow(fr); if(cnt[3]){ ans+=mint(cnt[0])*cnt[3]*mint(26).pow(fr-1); ans+=mint(cnt[2])*cnt[3]*mint(26).pow(fr-1); if(cnt[3]>=2){ ans+=mint(cnt[3])*(cnt[3]-1)*mint(26).pow(fr-2); } } } cout<