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>
using namespace std;
#define int long long
const int N=305,M=1e9+7;
char s[N];
int n,K,ans,a[N],fac[N],inv[N];
int C(int x,int y){
	return fac[x]*inv[y]%M*inv[x-y]%M;
}
void Check(int num,int sum){
	int pos=num+1,res=fac[num],rnum=0,leftr=0,nxt=0,left=0;
	for (int i=1;i<=K;i++)
		if (s[i]=='r'){
			if (rnum<num)leftr+=a[++rnum]>1;
			else if (left)left--;
		}
		else {
			if (leftr)leftr--,left+=a[++nxt]-2;
			else if (left)left--;
		}
	if (left||rnum<num||leftr) return;
	for (int i=1,j=1;i<=num;i=j){
		while (j<=num&&a[j]==a[i])j++;
		(res*=inv[j-i])%=M;
		pos+=(j-i)*(a[i]*2-1);
	}
	(ans+=res*C(n-sum+pos-1,pos-1))%=M;
}
void dfs(int x,int num,int sum){
	if (sum>n)return;
	Check(num,sum);
	for (int i=x;i;i--){
		a[num+1]=i;
		dfs(i,num+1,sum+(i>1?i*2-3:1)+(num>0));
	}
}
int ksm(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=x*x%M)
		if (y&1)(ans*=x)%=M;
	return ans;
}
signed main(){
	scanf("%lld%lld%s",&n,&K,s+1);
	fac[0]=inv[0]=1;
	for (int i=1;i<N;i++)fac[i]=fac[i-1]*i%M,inv[i]=ksm(fac[i],M-2);
	dfs(70,0,0); 
	printf("%lld\n",ans);
	return 0;
}