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
using namespace std;
const int mod=1e9+7;
int n,k;
char s[75],vis[75];
int len[75],tag[75];
ll ans,fac[205],finv[205],C[205][205];
inline bool check(int cnt){
	memset(vis,0,sizeof(vis));
	memset(tag,0,sizeof(tag));
	int fr=1,fb=1,now=0;
	for(int i=cnt;i;--i){
		if(len[i]==1){
			while(fr<=k&&s[fr]!='r') ++fr;
			if(fr>k) return 0;
			vis[fr++]=1;
		}
		else{
			while(fr<=k&&s[fr]!='r') ++fr;
			while(fb<=k&&(fb<=fr||s[fb]!='b')) ++fb;
			if(fr>k||fb>k) return 0;
			vis[fr++]=vis[fb++]=1; tag[max(fr,fb)-1]+=len[i]-2;
		}
	}
	for(int i=k;i;--i){
		if(!vis[i]) ++now;
		else now-=tag[i];
		if(now<0) return 0;
	}
	return 1;
}
bool dfs(int sum,int lst,int cnt,int tot){
	if(tot<0||!check(cnt)) return 0;
	int num=cnt+1;
	for(int i=1;i<=cnt;++i) num+=len[i]*2-1;
	ll now=C[tot+num-1][tot]*fac[cnt]%mod;
	for(int i=1,sz=len[cnt+1]=0;i<=cnt+1;++i) if(len[i]==len[i-1]) ++sz; else now=now*finv[sz]%mod,sz=1;
	(ans+=now)%=mod;
	for(int i=lst;i<=k-sum;++i){
		len[cnt+1]=i;
		if(!dfs(sum+i,i,cnt+1,tot-(i<=2?1:i*2-3)-(cnt>0))) return 1;
	}
	return 1;
}
inline ll qpow(ll x,int k,ll r=1){
	for(;k;k>>=1,x=x*x%mod) if(k&1) r=r*x%mod;
	return r;
}
int main(){
	scanf("%d%d%s",&n,&k,s+1);
	for(int i=fac[0]=1;i<=200;++i) fac[i]=fac[i-1]*i%mod;
	finv[200]=qpow(fac[200],mod-2);
	for(int i=200;i;--i) finv[i-1]=finv[i]*i%mod;
	for(int i=0;i<=200;++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(0,1,0,n);
	return printf("%lld\n",ans),0;
}