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>
const int mo=1e9+7,N=75;
int n,K,i,j,k,s1,s2,C[N*2][N*2],st[N],w,b,x,y,ans=1,a[N];
char c[N];
void dfs(int d,int s,int ss,bool fl){
	if(fl){
		for(i=1,j=k=w,b=0;i<=K;++i){
			if(c[i]=='r'){if(j)--j;else if(b)--b;}
			if(c[i]=='b'){if(k>j && st[k])b+=st[k--]-1;else if(b)--b;}
		}
		if(!j && !st[k] && !b){
			s1=s-1,s2=ss+1,x=C[n-s1+s2-1][s2-1];y=0;
			for(i=0;i<d;++i)y+=a[i],x=1ll*C[y][a[i]]*x%mo;
			ans=(ans+x)%mo;
		}
	}
	if(s+(d<2?1:d*2-1)>n)return;
	int ow=w;
	for(int i=0,j;s+i*(d<2?1:d*2-1)+i-1<=n;st[++w]=d,++i)
		a[d]=i,dfs(d+1,s+i*(d<2?1:d*2-1)+i,ss+i*(d*2+1)+i,i);
	w=ow;
}
int main(){
	for(i=**C=1;i<N*2;++i)for(j=*C[i]=1;j<=i;++j)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
	scanf("%d%d%s",&n,&K,c+1);
	dfs(0,0,0,0);
	printf("%d\n",ans%mo);
	return 0;
}