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 ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
using namespace std;
const int mo=1000000007;
const int N=750;
int C[N][N],n,k,ans;
int used[N],q1[N],q2[N];
int suf[N],a[N];
char s[N];
void init(){
	For(i,0,N-1) C[i][0]=1;
	For(i,1,N-1) For(j,1,i)
		C[i][j]=(C[i-1][j]+C[i-1][j-1])%mo;
}
void solve(int S){
	if (!S) return ++ans,void(0);
	memset(used,0,sizeof(used));
	int rest=S-a[1],h=0,t=*q2=0;
	For(i,1,k)
		if (s[i]=='r') q1[++t]=i;
		else if (s[i]=='b'&&h!=t&&*q2!=rest)
			used[q1[++h]]=used[i]=1,q2[++*q2]=i;
	//printf("%d %d %d\n",rest,*q2,ans);
	//For(i,1,n) printf("%d ",a[i]); puts("");
	if (*q2!=rest) return;
	For(i,1,a[1])
		if (h==t) return;
		else used[q1[++h]]=1;
	//printf("%d %d %d\n",rest,*q2,ans);
	//For(i,1,max(n,k)) printf("%d ",a[i]); puts("");
	Rep(i,k,1) suf[i]=suf[i+1]+(!used[i]);
	For(i,1,S-a[1]) q2[i]=suf[q2[i]];
	int posi=S-a[1],sum=0,par=0;
	For(i,2,n) For(j,1,a[i]){
		sum+=i-2;
		if (sum>q2[posi]) return;
		--posi; 
	}
	int v=1,s=a[1];
	sum=a[1]+S-1;
	par=S+1+a[1];
	For(i,2,max(2,n)){
		v=1ll*v*C[s+a[i]][s]%mo;
		sum+=a[i]*(2*i-3);
		par+=a[i]*(2*i-1);
		s+=a[i]; 
	}
	if (sum>n) return;
	//printf("%d %d %d\n",sum,par,v);
	v=1ll*v*C[n-sum+par-1][par-1]%mo;
	ans=(ans+v)%mo;
}
/*

*/
void dfs(int x,int xx,int y,int S){
	if (y>x||2*max(y-1,1)>xx) return solve(S);
	for (a[y]=0;x>=0&&xx>=0;++a[y],++S)
		dfs(x,xx,y+1,S),x-=y,xx-=2*max(y-1,1);
	a[y]=0;
}
int main(){
	init();
	scanf("%d%d",&n,&k);
	scanf("%s",s+1);
	dfs(k,n+1,1,0);
	printf("%d\n",ans);
}
/*
40 4
rrbb
*/