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 syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

ll Pow(ll n,ll p){
	ll r=1;
	for(;p>0;p>>=1){
		if(p&1) r=(r*n)%mod;
		n=(n*n)%mod;
	}
	return r;
}

const int M=200;
ll F[M];

void Init(){
	F[0]=1;
	for(int i=1;i<M;i++) F[i]=F[i-1]*i%mod;
}

ll Div(ll n,ll m){
	return n*Pow(m,mod-2)%mod;
}

ll nCk(ll n,ll k){
	return Div(F[n],F[n-k]*F[k]%mod);
}

ll nHr(ll n,ll r){
	return nCk(n+r-1,r);
}

int n,m;
vi a;

int main(){
	Init();
	cin>>n>>m;
	a=vi(m);
	for(int i=0;i<m;i++){
		char c;
		cin>>c;
		if(c=='b') a[i]++;
	}
	ll res=1;
	for(int i=0;i<=n;i++) for(int j=0;j<=n;j++){
		vi b(m),c(i);
		int A=0,B=0,C=0;
		for(int k=0;k<m;k++){
			if(!a[k]&&A+B!=i) A++,b[k]=1;
			else if(a[k]&&A) A--,b[k]=1,c[B++]=k;
		}
		for(int k=0;k<m;k++) if(a[k]+b[k]==0&&C<j) C++,b[k]=1;
		if(B!=i||C!=j||2*i+2*j-1>n||i+j==0) continue;
		for(int k=0;k<i;k++){
			int l=c[k];
			c[k]=0;
			while(l<m) c[k]+=1-b[l++];
			c[k]=min(c[k],(n-2*i-2*j+1)/2);
		}
		c.push_back(0);
		reverse(c.begin(),c.end());
		vvl dp(i+1,vl(n+1));
		dp[0][0]=Div(F[i+j],F[j]);
		for(int k=0;k<n;k++) for(int I=i;I>=0;I--) for(int J=0;J<=c[I];J++) for(int l=1;I+l<=i&&J+k*l<=c[I+l];l++){
			dp[I+l][J+k*l]+=Div(dp[I][J],F[l]);
		}
		for(int k=0;k<=c[i];k++) (res+=dp[i][k]*nHr(2*k+4*i+2*j+1,n-2*k-2*i-2*j+1))%=mod;
	}
	cout<<res<<endl;
}