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 unsigned long long ull;
typedef long double ld;
#define mp make_pair
#define PI pair<int,int>
#define poly vector<ll>
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
#define fi first
#define se second
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=105,mod=1e9+7,M=205;
char ch[N];
ll c[M][M];
int s[N],ans,n,len,sum[N];
ll dp[N][N];
ll hf(int a,int b){
	return a>=0&&b>=0?c[a+b-1][b-1]:0;
}
inline void add(int &a,ll b){
	a=(a+b)%mod;
	//cout<<a<<" "<<b<<endl;
}
bool vis[N];
int sss[N];
void woliekai(int x,int y){
	if(x+y==0){
		ans++; return;
	}
	memset(vis,0,sizeof(vis));
	vector<int> F,G;
	for(int i=1,ff=0;i<=len;i++)if(ch[i]=='r'){
		if(F.size()<y){F.pb(i); vis[i]=1;}
	}else {
		if(G.size()<F.size()){G.pb(i); vis[i]=1;}
		//if(y==2)cout<<sss[i+1]<<"faspogpoa"<<endl;
		//assert(sss[i]+1!=len-i+2);
	}
	int X=0;
	For(i,1,len)if(X<x&&!vis[i]&&ch[i]=='r'){vis[i]=1; X++;}
	if(X<x||G.size()<y)return;
	Rep(i,len,1)sss[i]=sss[i+1]+1-vis[i];
	For(i,1,y)sum[i]=sss[G[i-1]+1];
	reverse(sum+1,sum+y+1);
	//For(i,1,y)wri(sum[i]); puts("gfashiognoa"); 
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	For(i,2,(n+3)/2){
		Rep(k,y,0)Rep(j,n,0)if(dp[j][k]){
			int dk=k,dj=j;
			For(l,1,y-k){
				dk++; dj+=i*2-3;
				//if(l==2)cout<<l<<" "<<sum[dk]<<" "<<dj<<endl;
				//assert((dj+3*dk)%2==0);
				if(sum[dk]<(dj+3*dk)/2-2*dk||dj>n)break;
				//cout<<i<<" "<<l<<" "<<dj<<" "<<dk<<endl;
				
				dp[dj][dk]=(dp[dj][dk]+dp[j][k]*hf(l,k+1))%mod;
			}
		}
	}
	//cout<<dp[0][0]<<endl;
	Rep(j,n,0)if(dp[j][y]){
		//cout<<hf(x,y+1)<<" "<<n-(x+y-1)-j<<" "<<x+y+1+j+2*y<<" "<<hf(5,2)<<endl;
		ans=(ans+hf(x,y+1)*hf(n-(x+y-1)-j-x,x+y+1+j+x+2*y)%mod*dp[j][y])%mod;//x+y-1段w非空,x+j段非空,2段空,2y空 
		//cout<<dp[j][y]<<" "<<j<<" "<<y<<" "<<ans<< " "<<n-(x+y-1)-j-x<<" "<<x+y+1+j+x+2*y<<endl;
	}
	///if(y==2)exit(0);
//cout<<x<<" "<<y<<" "<<ans<<endl; //exit(0);
}
signed main(){
	//freopen("cover.in","r",stdin); freopen("cover.out","w",stdout);
	n=read(),len=read();
	For(i,0,M-1)For(j,c[i][0]=1,i)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	scanf("%s",ch+1);
	For(i,0,(n+1)/2){
		For(j,0,(n+1)/2-i)woliekai(i,j);
		//cout<<ans<<endl;
		//For(j,1,len)wri(vis[j]); puts("");
	}
	cout<<ans<<endl;
}
/*
7 5
rrbrb

*/