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 rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
typedef long long ll;
typedef pair<int,int> pii;

const int maxn=75;
const int mod=1e9+7;
int n,k;
char s[maxn];
int nxt[maxn][2],pos0[maxn],pos1[maxn],lim[maxn],fac[maxn*2],ifac[maxn*2];
int dp[maxn][maxn][maxn];
bool del[maxn];
void Add(int &a,int b){
	a+=b;
	if(a>=mod)a-=mod;
}
int C(int a,int b){
	if(a<b||a<0||b<0)return 0;
	return 1LL*fac[a]*ifac[b]%mod*ifac[a-b]%mod;
}

int main(){
	scanf("%d%d%s",&n,&k,s);
	fac[0]=fac[1]=ifac[0]=ifac[1]=1;
	for(int i=2;i<=2*max(n,k);i++){
		fac[i]=1LL*fac[i-1]*i%mod;
		ifac[i]=1LL*ifac[mod%i]*(mod-mod/i)%mod;
	}
	REP(i,2*max(n,k))ifac[i]=1LL*ifac[i-1]*ifac[i]%mod;
	nxt[k][0]=nxt[k][1]=k;
	for(int i=k-1;i>=0;i--){
		if(s[i]=='r')nxt[i][0]=i,nxt[i][1]=nxt[i+1][1];
		else nxt[i][0]=nxt[i+1][0],nxt[i][1]=i;
	}
	int ans=0;
	rep(i,k+1)rep(s,k+1){
		bool ok=true;
		int last0=-1,last1=-1;
		rep(j,k)del[j]=false;
		rep(j,i){
			pos0[j]=nxt[last0+1][0];
			pos1[j]=nxt[max(last1+1,pos0[j])][1];
			if(pos0[j]==k||pos1[j]==k){
				ok=false;
				break;
			}
			del[pos0[j]]=del[pos1[j]]=true;
			last0=pos0[j];last1=pos1[j];
		}
		if(!ok)continue;
		int last=-1;
		rep(j,s){
			int cur0=nxt[last+1][0];
			while(cur0<k&&del[cur0])cur0=nxt[cur0+1][0];
			if(cur0==k){
				ok=false;
				break;
			}
			del[cur0]=true;
		}
		if(!ok)continue;
		rep(j,i){
			lim[i-j]=0;
			for(int p=pos1[j]+1;p<k;p++)if(!del[p])lim[i-j]++;
		}
		memset(dp,0,sizeof(dp));
		dp[0][0][0]=1;
		rep(j,i+1)rep(p,k+1)rep(q,k+1){
			int cur=dp[j][p][q];
			if(!cur)continue;
			rep(t,k+1){
				if(q+t*p>lim[j+t])break;
				Add(dp[j+t][p+1][q+t*p],1LL*cur*ifac[t]%mod);
			}
		}
		rep(q,k+1){
			int cur=dp[i][k][q];
			if(!cur)continue;
			int now=q*2+i;
			int coef=1LL*cur*fac[i+s]%mod*ifac[s]%mod;
			rep(p,n-s-now+1){
				int cur;
				if(now+2*i+s==0&&p==0)cur=1;
				else cur=1LL*C(p+(now+2*i+s-1),now+2*i+s-1)*C(n-s-now-p+1,i+s)%mod;
				Add(ans,1LL*coef*cur%mod);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}