Problem: There are N white balls arranged in a row, numbered 1,2,..,N from left to right. AtCoDeer the deer is thinking of painting some of these balls red and blue, while leaving some of them white.

You are given a string s of length K. AtCoDeer performs the following operation for each i from 1 through K in order:

* The i-th operation: Choose a contiguous segment of balls (possibly empty), and paint these balls red if the i-th character in s is `r`; paint them blue if the character is `b`.



Here, if a ball which is already painted is again painted, the color of the ball will be overwritten. However, due to the properties of dyes, it is not possible to paint a white, unpainted ball directly in blue. That is, when the i-th character in s is `b`, the chosen segment must not contain a white ball.

After all the operations, how many different sequences of colors of the balls are possible? Since the count can be large, find it modulo 10^9+7.

Constraints

* 1 ≤ N ≤ 70
* 1 ≤ K ≤ 70
* |s| = K
* s consists of `r` and `b`.
* N and K are integers.

Input

Input is given from Standard Input in the following format:


N K
s


Output

Print the number of the different possible sequences of colors of the balls after all the operations, modulo 10^9+7.

Examples

Input

2 2
rb


Output

9


Input

5 2
br


Output

16


Input

7 4
rbrb


Output

1569


Input

70 70
bbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr


Output

841634130

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define mem(x,v) memset(x,v,sizeof(x))
#define Rep(i,a,b) for(register int i=(a);i<=int(b);++i)
#define rep(i,a,b) for(register int i=(a);i<int(b);++i)
#define Dep(i,a,b) for(register int i=(a);i>=int(b);--i)
#define gc getchar
#define pc putchar
#define fi first
#define se second
inline ll read(){
    ll x=0;int f=1;char c=gc();
    for(;!isdigit(c);c=gc())if(c=='-')f=-1;
    for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
    return x*f;
}
inline void write(ll x){if(x<0)x=-x,pc('-');if(x>=10)write(x/10);putchar(x%10+'0');}
inline void writeln(ll x){write(x);pc('\n');}
inline void wri(ll x){write(x);pc(' ');}
const int maxn = 255;
const int mod = 1e9+7;
int n,m;
char s[maxn];
int ans,fac[maxn],ifac[maxn];
inline int qpow(int a,int b){
	int ans=1;
	for(;b;b>>=1,a=1ll*a*a%mod)
		if(b&1) ans=1ll*ans*a%mod;
	return ans;
}
void init(){
	n = read(),m = read();
	scanf("%s",s+1);
	fac[0] = 1;rep(i,1,maxn) fac[i] = 1ll * fac[i-1] * i % mod;
	ifac[maxn-1] = qpow(fac[maxn-1],mod-2);
	Dep(i,maxn-2,0) ifac[i] = 1ll * ifac[i+1] * (i+1) % mod;
	assert(ifac[0]==1);
}
inline int C(int n,int m){
	return 1ll * fac[n] * ifac[m] % mod * ifac[n-m] % mod;
}
#define cal(x,y) C((x)+(y)-1,(y)-1)
int g[maxn],a[maxn];
void calc(int w,int tot){
	Rep(i,1,tot) a[i] = g[tot-i+1];a[tot+1]=0;
	int lim=0;while(lim<tot && a[lim+1]>1) ++lim;
	int i,j,k,l,t;
	for(i=1,k=1,l=1,t=0;i<=m;++i){
		if(s[i]=='r' && k<=tot) 
		k++; else
		if(s[i]=='b' && l<k && l<=lim) t+=a[l]-2,l++; else
		if(t) t--; 
	}
	if(k<=tot || l<=lim || t) return ;
	int pos=tot+1,res=fac[tot];
	for(i=1;i<=tot;i=j+1){
		for(j=i;a[j+1]==a[i];++j);
		res=1ll*res*ifac[j-i+1]%mod;
		pos+=(j-i+1)*(2*a[i]-1);
	}
	ans=(ans+1ll*res*cal(w,pos))%mod;
}
void dfs(int w,int z,int last){
	calc(w,z-1);
	if(last==1&&w-1>=0) g[z]=1,dfs(w-1-(z>1),z+1,1); 
	for(int i=max(2,last);w-(i-1)-(i-2)>=0;++i){
		g[z] = i,dfs(w-(i-1)-(i-2)-(z>1),z+1,i);
	}
	g[z] = 0;
}
int main(){
	ans=0;
	init(); 
	dfs(n,1,1);
	writeln(ans);
}