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>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define div _zzd001
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"-----------------"#x"-----------------\n"
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
                    For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> pii;
LL read(){
    LL x=0,f=0;
    char ch=getchar();
    while (!isdigit(ch))
        f=ch=='-',ch=getchar();
    while (isdigit(ch))
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int N=75*2,mod=1e9+7;
int Pow(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=(LL)x*x%mod)
		if (y&1)
			ans=(LL)ans*x%mod;
	return ans;
}
void Add(int &x,int y){
	if ((x+=y)>=mod)
		x-=mod;
}
void Del(int &x,int y){
	if ((x-=y)<0)
		x+=mod;
}
int Add(int x){
	return x>=mod?x-mod:x;
}
int Del(int x){
	return x<0?x+mod:x;
}
int n,k;
int C[N][N];
char s[N];
vector <int> div;
int ans=0;
int cr=0,cb=0;
void Solve(){
//	ans++;
//	outarr(div,0,(int)div.size()-1);
	int nr=0,nb=0;
	for (auto i : div)
		nr++,nb+=i>1;
	if (nr>cr||nb>cb)
		return;
	static int a[N],rem[N];
	clr(a),clr(rem);
	int m=div.size();
	For(i,0,m-1)
		a[i+1]=div[i];
	reverse(a+1,a+m+1);
	int pp=0;
	For(i,1,m)
		if (a[i]>1)
			pp=i;
	int need=0,p=0,sp=0;
	For(i,1,k)
		if (s[i]=='r'&&p<m){
			p++;
		}
		else if (s[i]=='b'){
			if (sp<min(p,pp)){
				need+=a[++sp]-2;
			}
			else if (need>0)
				need--;
		}
		else if (need>0){
			need--;
		}
	if (need>0||sp<pp)
		return;
	static int dp[N];
	static int cs[4]={0,0,1,0};
	clr(dp);
	dp[0]=1;
	for (auto i : div){
		Fod(j,n,0){
			if (!dp[j])
				continue;
			Fod(k,3,1){
				if (j+i*2-k+1>n)
					break;
				if (i==1&&k>1)
					continue;
				Add(dp[j+i*2-k+1],Add(dp[j]<<cs[k]));
			}
			dp[j]=0;
		}
	}
	int tmp=0;
//	outarr(dp,0,n);
	For(i,0,n)
		if (dp[i])
			Add(tmp,(LL)dp[i]*C[n][i]%mod);
	int las=1;
	a[m+1]=-1;
	int s=0;
	For(i,2,m+1){
		if (a[i]!=a[i-1]){
			int len=i-las;
			las=i;
			tmp=(LL)tmp*C[s+=len][len]%mod;
		}
	}
//	outval(tmp);
	Add(ans,tmp);
}
void dfs(int rem,int n,int now,int flag){
	if (n<0)
		return;
	if (flag)
		Solve();
	if (rem>=now){
		div.pb(now);
		dfs(rem-now,n-max(1,now*2-3)-1,now,1);
		div.pop_back();
		dfs(rem,n,now+1,0);
	}
}
int main(){
	For(i,0,N-1)
		C[i][0]=1;
	For(i,1,N-1)
		For(j,1,i)
			C[i][j]=Add(C[i-1][j-1]+C[i-1][j]);
	n=read()+1,k=read();
	cin>>(s+1);
	For(i,1,k)
		if (s[i]=='r')
			cr++;
		else
			cb++;
	div.clear();
	dfs(k,n,1,1);
	cout<<ans<<endl;
	return 0;
}