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:
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#define N 75
#define ll long long
#define mo 1000000007
ll qpow(ll x,ll y=mo-2){
	ll r=1;
	for (;y;y>>=1,x=x*x%mo)
		if (y&1)
			r=r*x%mo;
	return r;
}
ll fac[N*4],ifac[N*4];
void initC(int n){
	fac[0]=1;
	for (int i=1;i<=n;++i)
		fac[i]=fac[i-1]*i%mo;
	ifac[n]=qpow(fac[n]);
	for (int i=n-1;i>=0;--i)
		ifac[i]=ifac[i+1]*(i+1)%mo;
}
ll inv(int n){return ifac[n]*fac[n-1]%mo;}
ll C(int m,int n){
	if (m<n) return 0;
	return fac[m]*ifac[n]%mo*ifac[m-n]%mo;
}
int n,K;
char str[N];
int p[N],m;
ll ans;
bool judge(){
	static int q[N],need[N];
	static int used[N];
	int head=1,tail=0;
	memset(used,255,sizeof(int)*(K+1));
	int i=1,j=1;
	for (;j<=K && i<=m && p[i]>1;++j){
		if (head<=tail && str[j]=='b')
			used[j]=p[i++]-2,used[q[head++]]=0;
		else if (str[j]=='r')
			q[++tail]=j;
	}
	if (i<=m && p[i]>1) return 0;
	for (;j<=K;++j)
		if (str[j]=='r')
			q[++tail]=j;
	for (;i<=m;++i){
		if (head>tail) return 0;
		used[q[head++]]=0;
	}
	int cnt=0;
	for (int j=K;j>=1;--j){
		if (used[j]==-1)
			cnt++;
		else if (used[j]>0){
			if (cnt<used[j]) return 0;
			cnt-=used[j];
		}
	}
	return 1;
}
ll calc(){
//	for (int i=1;i<=m;++i)
//		printf("%d ",p[i]);
//	printf("\n");
	if (m==0) return 1;
	p[m+1]=-1;
	ll s=fac[m];
	for (int i=1,j=0;i<=m;++i){
		j++;
		if (p[i]!=p[i+1]){
			s=s*ifac[j]%mo;
			j=0;
		}
	}
	ll c0=2,c1=m-1;
	for (int i=1;i<=m;++i){
		if (p[i]==1)
			c1++;
		else{
			c1+=2*p[i]-3;
			c0+=2;
		}
	}
	s=s*C((n-c1)+(c1+c0)-1,n-c1)%mo;
//	printf("ans=%lld\n",s);
	return s;
}
void dfs(int s,int k){
	if (judge())
		ans+=calc();
	if (s==0)
		return;
	for (int i=k;i>=1;--i){
		if (s>=2*i-1+(s!=n)){
			p[++m]=i+1;
			dfs(s-(2*i-1)-(s!=n),i);
			--m;
		}
	}
	if (s>=1+(s!=n)){
		p[++m]=1;
		dfs(s-1-(s!=n),0);
		--m;
	}
}
int main(){
//	freopen("in.txt","r",stdin);
	scanf("%d%d%s",&n,&K,str+1);
	initC(n*4);
	dfs(n,n);
	ans%=mo;
	printf("%lld\n",ans);
	return 0;
}