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;
template<typename tn> void read(tn &a){
	tn x=0,f=1; char c=' ';
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	a=x*f;
}
const int mod = 1e9+7;
vector<int> V;
int C[210][210],n,len;
char S[210];
ll ans;
ll fp(ll a,ll k){
	ll ans=1;
	for(;k;k>>=1,a=a*a%mod)
		if(k&1) ans=a*ans%mod;
	return ans;
}
void calc(){
	int nd=0,k1=0,k2=0;
	for(int i=1;i<=len;i++){
		if(k1<V.size()&&S[i]=='r') k1++;
		else if(k2<k1&&V[k2]>0&&S[i]=='b') nd+=V[k2++]-1;
		else if(nd) nd--;
	}
	if(nd||k1<V.size()||k2<k1&&V[k2]>0) return;
//	for(auto x:V) cerr<<x<<' ';cerr<<'\n';
	int used=V.size()-1,pos=used+2;
	for(int i=0;i<V.size();i++) used+=max(1,V[i]*2-1),pos+=V[i]*2+1;
	ll now=C[pos+n-used-1][n-used];
	ll p=0,res=1;
	for(int i=0;i<V.size();i++){
		if(i==0||V[i]==V[i-1]){
			res=res*++p%mod;
		}
		else now=now*fp(res,mod-2)%mod,res=1,p=1;
		now=now*(i+1)%mod;
	}
	ans=(ans+now*fp(res,mod-2))%mod;
}
void solve(int n,int lim){
	if(V.size()) calc();
	for(int i=lim;~i;i--)
		if(max(1,2*i-1)<=n){
			if(max(1,2*i-1)==n&&V.size()) continue;
			V.push_back(i);
			solve(n-max(2*i-1,1)-(V.size()!=1),i);
			V.pop_back();
		}
}
int main(){
	read(n);read(len);
	cin>>S+1;ans=1;
	for(int i=0;i<=150;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	}
	solve(n,n);
	cout<<ans<<'\n';
	return 0;
}