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<cstdio>
#include<algorithm>
using namespace std;
const int N=233;
const int mod=1e9+7;
int n,k,inv[N],jc[N],jcn[N],a[N],ans;
char str[N];
int C(int x,int y){
	return 1ll*jc[x]*jcn[y]%mod*jcn[x-y]%mod;
}
int cal(int x,int y){
	return C(x+y-1,y-1);
}
void check(int y,int z){
	int lim=0;while(lim<y&&a[lim+1]>1)++lim;
	int cnt_r=0,cnt_b=0,cnt=0;
	for(int i=1;i<=k;++i)
		if(str[i]=='r'&&cnt_r<y)
			++cnt_r;
		else if(str[i]=='b'&&cnt_b<min(cnt_r,lim))
			++cnt_b,cnt+=a[cnt_b]-2;
		else if(cnt)
			--cnt;
	if(cnt_r<y||cnt_b<lim||cnt)return;
	int pos=y+1,res=jc[y];
	for(int i=1,j=1;i<=y;i=j=j+1){
		while(j<y&&a[j+1]==a[i])++j;
		res=1ll*res*jcn[j-i+1]%mod;
		pos+=(j-i+1)*(a[i]+a[i]-1);
	}
	ans=(ans+1ll*res*cal(n-z,pos))%mod;
}
void dfs(int x,int y,int z){
	if(z>n)return;check(y,z);
	for(int i=x;i;--i)a[y+1]=i,dfs(i,y+1,z+(y>0)+(i>1?i+i-3:1));
}
int main(){
	scanf("%d%d%s",&n,&k,str+1);
	jc[0]=jcn[0]=inv[1]=1;
	for(int i=2;i<N;++i)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
	for(int i=1;i<N;++i)jc[i]=1ll*jc[i-1]*i%mod,jcn[i]=1ll*jcn[i-1]*inv[i]%mod;
	dfs(70,0,0);printf("%d\n",ans);return 0;
}