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 maxn 75
using namespace std;
const int mod = 1e9+7;
int n,k,m,a[maxn],x[maxn],C[maxn*2][maxn*2],ans=1;
char s[maxn];
void dfs(int d,int l,int r,bool chose){
	if(chose){
		int R=1,B=1,S=0;
		for(int i=1;i<=k;i++){
			if(s[i]=='r') {if(R<=m) R++; else if(S) S--;}
			if(s[i]=='b') {if(B<R&&x[B]) S+=x[B++]-1; else if(S) S--;}
		}
		if(R>m&&(B>m||!x[B])&&!S){
			int ret=C[n-l+r][r];
			for(int i=d+1;i<=x[1];i++) S+=a[i],ret=1ll*ret*C[S][a[i]]%mod;
			ans=(ans+ret)%mod;
		}
	}
	if(d<0) return;
	int tm=m,tl=(d?2*d-1:1),tr=2*d+1;
	for(int i=0;l<=n;x[++m]=d,l+=tl+(l!=0),r+=tr+1,i++) 
		a[d]=i,dfs(d-1,l,r,i);
	m=tm;
}
int main()
{
	scanf("%d%d%s",&n,&k,s+1);
	for(int i=C[0][0]=1;i<150;i++) for(int j=C[i][0]=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	dfs(n,0,0,0);
	printf("%d\n",ans);
}