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<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#define LL long long
#define LD long double
using namespace std;
const int NN=1 +117;
const int MM=1 +117;
int read(){
	int fl=1,x;char c;
	for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
	if(c=='-'){fl=-1;c=getchar();}
	for(x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<3)+(x<<1)+c-'0';
	return x*fl;
}
void open(){
	freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
}
void close(){
	fclose(stdin);
	fclose(stdout);
}

const int mod=1e9+7;
int k,n;
LL fact[4*NN]={};
LL rev[4*NN]={};
char s[NN]={};
LL ksm(LL a,LL b){
	LL ret=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1)ret=a*ret%mod;
	return ret;
}
LL comp(int n,int m){
	return fact[n]*rev[m]%mod*rev[n-m]%mod;
}
void prefact(int n){
	fact[0]=1;
	for(int i=1;i<=n;++i)fact[i]=fact[i-1]*i%mod;
	rev[n]=ksm(fact[n],mod-2);
	for(int i=n;i>=1;--i){
		rev[i-1]=rev[i]*i%mod;
	}
}
int seq[NN][2]={},scnt=0;
LL ans=0;
int len[NN]={};
int pos[NN]={};
bool used[NN]={};
int rcnt=0;
int bcnt=0;
void calc(){
	int tp=0;
	for(int i=1;i<=k;++i)used[i]=0;
	for(int i=1;i<=scnt;++i){
		for(int j=1;j<=seq[i][1];++j){
			len[++tp]=seq[i][0];
			pos[tp]=0;
		}
	}
	int now=1;
	for(int i=1;i<=k;++i){
		if(!used[i]&&s[i]=='r'&&now<=tp&&pos[now]<i){
			--len[now],pos[now]=i,++now,used[i]=1;
		}
	}
	if(now!=tp+1)return ;
	now=1;
	while(now<=tp&&!len[now])++now;
	for(int i=1;i<=k;++i){
		if(!used[i]&&s[i]=='b'&&now<=tp&&pos[now]<i){
			--len[now],pos[now]=i,used[i]=1;
			++now;
			while(now<=tp&&!len[now])++now;
		}
	}
	if(now!=tp+1)return ;
	now=1;
	while(now<=tp&&!len[now])++now;
	for(int i=1;i<=k;++i){
		if(!used[i]&&now<=tp&&pos[now]<i){
			--len[now],pos[now]=i,used[i]=1;
			while(now<=tp&&!len[now])++now;
		}
	}
	if(now!=tp+1)return ;
	int les=tp-1;
	if(tp==0)les=1;
	int seg=tp+1;
	LL ad=fact[tp];
	for(int i=1;i<=scnt;++i){
		ad=ad*rev[seq[i][1]]%mod;
		int l=seq[i][0];
		for(int j=1;j<=seq[i][1];++j){
			if(l==1)les+=1;
			else les+=2*l-3;
			seg+=2*l-1;
		}
	}
	if(les>n)return ;
	//for(int i=1;i<=scnt;++i)cerr<<seq[i][0]<<":"<<seq[i][1]<<endl;
	//cerr<<endl;
	//cerr<<ad<<" "<<seg<<" "<<n-les<<endl;
	ad=ad*comp(n-les+seg-1,n-les)%mod;
	ans=(ans+ad)%mod;
}
int all=-1;
int TEST=0;
void dfs(int rem,int now){
	if(all>n)return ;
	if(now==0){
		calc();
		//for(int i=1;i<=scnt;++i)cerr<<seq[i][0]<<":"<<seq[i][1]<<endl;
		//cerr<<endl;
		return ;
	}
	for(int i=0;i*now<=rem;++i){
		if(i){
			++scnt;
			seq[scnt][0]=now;
			seq[scnt][1]=i;
			if(now==1)all+=i;
			else all+=i*(2*now-3);
			all+=i;
		}
		dfs(rem-i*now,now-1);
		if(i){
			--scnt;
			if(now==1)all-=i;
			else all-=i*(2*now-3);
			all-=i;
		}
	}
}
int main(){
	//open();
	n=read();
	k=read();
	prefact(4*k+n+10);
	scanf("%s",s+1);
	for(int i=1;i<=k;++i)
		if(s[i]=='r')rcnt++;
		else bcnt++;
	dfs(k,k);
	printf("%lld\n",ans);
	//cerr<<TEST<<endl;
	close();
	return 0;
}