#include using namespace std; using ll=long long; #define int ll #define rng(i,a,b) for(int i=int(a);i=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int(x.size()) #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "< void chmax(t&a,u b){if(a void chmin(t&a,u b){if(b using vc=vector; template using vvc=vc>; using pi=pair; using vi=vc; template ostream& operator<<(ostream& os,const pair& p){ return os<<"{"< ostream& operator<<(ostream& os,const vc& v){ os<<"{"; for(auto e:v)os< void dmpr(ostream&os,const T&t,const Args&... args){ os< ostream& operator<<(ostream&os,const array&a){ return os<(all(a)); } template void print_tuple(ostream&,const T&){ } template void print_tuple(ostream&os,const T&t){ if(i)os<<","; os<(t); print_tuple(os,t); } template ostream& operator<<(ostream&os,const tuple&t){ os<<"{"; print_tuple<0,tuple,Args...>(os,t); return os<<"}"; } template void print(t x,int suc=1){ cout<>i; return i; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=read()+off; return v; } pi readpi(int off=0){ int a,b;cin>>a>>b; return pi(a+off,b+off); } template void print(const vector&v,int suc=1){ rep(i,v.size()) print(v[i],i==int(v.size())-1?suc:2); } string readString(){ string s; cin>>s; return s; } template T sq(const T& t){ return t*t; } //#define CAPITAL void yes(bool ex=true){ #ifdef CAPITAL cout<<"YES"<<"\n"; #else cout<<"Yes"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void no(bool ex=true){ #ifdef CAPITAL cout<<"NO"<<"\n"; #else cout<<"No"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void possible(bool ex=true){ #ifdef CAPITAL cout<<"POSSIBLE"<<"\n"; #else cout<<"Possible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void impossible(bool ex=true){ #ifdef CAPITAL cout<<"IMPOSSIBLE"<<"\n"; #else cout<<"Impossible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } constexpr ll ten(int n){ return n==0?1:ten(n-1)*10; } const ll infLL=LLONG_MAX/3; #ifdef int const int inf=infLL; #else const int inf=INT_MAX/2-100; #endif int topbit(signed t){ return t==0?-1:31-__builtin_clz(t); } int topbit(ll t){ return t==0?-1:63-__builtin_clzll(t); } int botbit(signed a){ return a==0?32:__builtin_ctz(a); } int botbit(ll a){ return a==0?64:__builtin_ctzll(a); } int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } bool ispow2(int i){ return i&&(i&-i)==i; } ll mask(int i){ return (ll(1)< void mkuni(vc&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } ll rand_int(ll l, ll r) { //[l, r] #ifdef LOCAL static mt19937_64 gen; #else static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count()); #endif return uniform_int_distribution(l, r)(gen); } template void myshuffle(vc&a){ rep(i,si(a))swap(a[i],a[rand_int(0,i)]); } template int lwb(const vc&v,const t&a){ return lower_bound(all(v),a)-v.bg; } vvc readGraph(int n,int m){ vvc g(n); rep(i,m){ int a,b; cin>>a>>b; //sc.read(a,b); a--;b--; g[a].pb(b); g[b].pb(a); } return g; } vvc readTree(int n){ return readGraph(n,n-1); } 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(initializer_listls):v(*ls.bg){} modular(ll vv=0){s(vv%mod+mod);} modular& s(uint vv){ v=vv>=1; } return res; } modular inv()const{return pow(mod-2);} /*modular inv()const{ int x,y; int g=extgcd(v,mod,x,y); assert(g==1); if(x<0)x+=mod; return modular(x); }*/ friend modular operator+(int x,const modular&y){ return modular(x)+y; } friend modular operator-(int x,const modular&y){ return modular(x)-y; } friend modular operator*(int x,const modular&y){ return modular(x)*y; } friend modular operator/(int x,const modular&y){ return modular(x)/y; } friend ostream& operator<<(ostream&os,const modular&m){ return os<>(istream&is,modular&m){ ll x;is>>x; m=modular(x); return is; } bool operator<(const modular&r)const{return v; const int vmax=1000; 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 choose(int n,int k){ return fact[n]*finv[n-k]*finv[k]; } mint binom(int a,int b){ return fact[a+b]*finv[a]*finv[b]; } mint catalan(int n){ return binom(n,n)-(n-1>=0?binom(n-1,n+1):0); } /* const int vmax=110; mint binbuf[vmax][vmax]; mint choose(int n,int k){ return binbuf[n-k][k]; } mint binom(int a,int b){ return binbuf[a][b]; } void initfact(){ binbuf[0][0]=1; rep(i,vmax)rep(j,vmax){ if(i)binbuf[i][j]+=binbuf[i-1][j]; if(j)binbuf[i][j]+=binbuf[i][j-1]; } } */ //initfact mint interpolate(const vc&a,mint x){ int n=si(a); if(inc(0,x.v,n-1))return a[x.v]; vc z(n+1); z[n]=1; per(i,n)z[i]=z[i+1]*(x-i); mint res,w=1; rep(i,n){ res+=w*z[i+1]*a[i]*finv[i]*finv[n-1-i]*((n-1-i)%2?-1:1); w*=x-i; } return res; } //VERIFTY:yosupo // f は k 次多項式を 0 から k で評価した値が入る //sum {0<=i<=n-1} a^i f[i] mint exp_poly_sum(const mint a,const vc&f,const int n){ if(n==0)return 0; int k=si(f)-1; if(a==0){ return f[0]; }else if(a==1){ vc g(k+2); rep(i,k+1)g[i+1]=g[i]+f[i]; return interpolate(g,n); }else{ vc g(k+1); { mint r=1; rep(i,k+1){ g[i]=f[i]*r; r*=a; } } mint c; { mint w,r=1; rep(i,k+1){ w+=choose(k+1,i)*r; r*=-a; c+=g[k-i]*w; } c/=mint(1-a).pow(k+1); } rep(i,k)g[i+1]+=g[i]; mint ainv=a.inv(),w=1; rep(i,k+1){ g[i]=(g[i]-c)*w; w*=ainv; } return interpolate(g,n-1)*a.pow(n-1)+c; } } const int mmax=105; mint small[mmax]; mint getpowsum(int n,int k,int s,vc vs,mint r){ assert(s>=0); mint w=mint(n).pow(k); r*=n; return exp_poly_sum(r,vs,s)*w; } mint subsum(int n,int k,int s,vc vs,mint r){ assert(s>=0); mint w=k==0?mint(n).inv():mint(n).pow(k-1); r*=n; rep(i,si(vs)) vs[i]*=n-k-i; return exp_poly_sum(r,vs,s)*w; } mint slv5(int a,int n,int k,int s,vc vs,mint r){ assert(a>=0); assert(inc(a,k,n)); mint res=getpowsum(n,k,s,vs,r); res-=subsum(n,k,s,vs,r)*a; if(a>=2){ chmin(s,n-1-k); if(s>=0){ rep(i,a-1){ res+=subsum(n-(i+1),k-i,s,vs,r)*(a-1-i)*small[i+1]; rep(j,si(vs)){ vs[j]*=k+j-i; vs[j]*=invs[i+1]; } } } } return res; } mint conv[mmax]; mint slv4(int a,int b,int n,int k,int s,vc vs,mint r){ assert(a>=0); assert(b>=0); assert(a+b+1<=n); assert(inc(a+b,k,n-1)); mint res=subsum(n,k,s,vs,r); chmin(s,n-1-k); if(s>=0){ rep(_,2){ rng(i,1,a+1){ vc tmp=vs; rep(j,si(tmp))tmp[j]*=choose(k+j,i-1); //res-=choose(k,i-1)*small[i]*sub(n-i,k-(i-1)); res-=subsum(n-i,k-(i-1),s,tmp,r)*small[i]; } swap(a,b); } } chmin(s,n-2-k); if(s>=0){ rep(sum,a+b-1){ vc tmp=vs; rep(j,si(tmp))tmp[j]*=choose(k+j,sum); res+=subsum(n-(sum+2),k-sum,s,tmp,r)*conv[sum]; //res+=choose(k,sum)*conv[sum]*sub(n-(sum+2),k-sum); } } return res; } signed main(){ cin.tie(0); ios::sync_with_stdio(0); cout<>n>>m; small[1]=1; rng(i,2,m+2){ small[i]=mint(i).pow(i-2); } vi ls; int cur=0; string str;cin>>str; int cnt=0; for(auto c:str){ if(c=='o'){ ls.pb(cur); cur=0; }else{ cnt++; cur++; } } ls.pb(cur); mint ans; const int d=m+5; if(si(ls)==1){ int k=cnt,s=n-cnt+1; ans+=slv5(ls[0],n,k,s,vc(d,1),mint(n).inv())*mint(n).pow(n-k); }else{ int a=ls[0],b=ls.back(); rep(i,a)rep(j,b){ conv[i+j]+=small[i+1]*small[j+1]*binom(i,j); } mint w=1; int u=0; rng(i,1,si(ls)-1){ w*=small[ls[i]+1]; w*=finv[ls[i]]; u+=ls[i]; } w*=fact[u]; int k=cnt,s=n-(si(ls)-1)+1-k; w*=mint(n).pow(n-k); vc vs(d); rep(i,d)vs[i]=choose(k+i,u); ans+=slv4(a,b,n-(si(ls)-2)-u,k-u,s,vs,mint(n).inv()); /*rng(k,cnt,n-(si(ls)-1)+1){ mint ad=slv4(a,b,n-(si(ls)-2)-u,k-u)*choose(k,u)*getpow(n,n-k); ans+=ad; }*/ ans*=w; } print(ans*(n-m+1)); }