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:
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#else
#define D(...) ((void)0)
#define NDEBUG
#endif
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
const int N=150,P=1e9+7;
int n,m,top,ans,st[N],fac[N],ifac[N],inv[N],beg[N];
char s[N];
bool vis[N];
int C(int k1,int k2){
	if(k1<0||k2<0||k1-k2<0)return 0;
	return 1LL*fac[k1]*ifac[k2]%P*ifac[k1-k2]%P;
}
bool chk(){
	rep(i,1,m)vis[i]=0;
	int ntop=top;
	rep(i,1,ntop)beg[i]=0;
	for(int i=1;i<=ntop;++i){
		beg[i]=max(beg[i],beg[i-1]+1);
		while(beg[i]<=m&&s[beg[i]]!='r')++beg[i];
		if(beg[i]>m)return 0;
		vis[beg[i]]=1;
		beg[i]=beg[i];
	}
	while(ntop&&st[ntop]==1)--ntop;
	for(int i=1;i<=ntop;++i){
		beg[i]=max(beg[i],beg[i-1]+1);
		while(beg[i]<=m&&s[beg[i]]!='b')++beg[i];
		if(beg[i]>m)return 0;
		vis[beg[i]]=1;
	}
	for(int i=1;i<=ntop;++i){
		beg[i]=max(beg[i],beg[i-1]+1);
		rep(_,1,st[i]-2){
			while(beg[i]<=m&&vis[beg[i]])++beg[i];
			if(beg[i]>m)return 0;
			vis[beg[i]]=1;
		}
	}
	return 1;
}
void dfs(int num,int mn,int mx,int ntop){
	if(!num){
		if(!chk())return;
		rep(i,1,top){
			D("%d ",st[i]);
		}
		D("\n");
		D(">>> %d %d\n",mn,mx);
		int ans=C(n-mn+mx-1,mx-1);
		while(ntop){
			int x=st[ntop];
			int t=0;
			while(st[ntop]==x)++t,--ntop;
			ans=1LL*ans*C(ntop+t,t)%P;
		}
		(::ans+=ans)%=P;
		return;
	}
	while(1){
		dfs(num-1,mn,mx,ntop);
		top=ntop;
		mn+=(num==1?1:2*num-3)+!!mn;
		if(mn>n)return;
		mx+=2*num;
		st[++top]=num;
		++ntop;
	}
}
int main(){
	fac[0]=fac[1]=inv[0]=inv[1]=ifac[0]=ifac[1]=1;
	for(int i=2;i<N;++i)fac[i]=1LL*fac[i-1]*i%P,inv[i]=1LL*(P-P/i)*inv[P%i]%P,ifac[i]=1LL*ifac[i-1]*inv[i]%P;
	scanf("%d%d%s",&n,&m,s+1);
	dfs(n+3,0,1,0);
	printf("%d\n",ans);
	return 0;
}

/*
1 35
rbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbr

3
*/

/*
30 35
rrrrrrrrrrrrrrrrrbbbbbbbbbbbbbbbbbb

130653412
*/