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
#define N 210
#define mo 1000000007 
using namespace std;
template <typename T> void read(T &x){
	x=0;char ch=getchar();int fh=1;
	while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=fh;
}
int m,n,a[N],f[N],nb,b[N],c[N];
ll jie[N],nj[N],ans;
ll po(ll x,ll y){ll z=1;while (y){if (y%2)z=x*z%mo;x=x*x%mo;y/=2;}return z;}
ll C(int x,int y){return (jie[x]*nj[y]%mo)*nj[x-y]%mo;}
void chk(){
	nb=0;memset(b,0,sizeof(b));
	for (int i=(n+1)/2;i>=0;i--)
		for (int j=1;j<=f[i];j++)b[++nb]=i;
	for (int i=1,n0=0,n1=0;i<=m;i++){
		c[i]=0;
		if (a[i]==0){n0++;if (n0<=nb)c[i]=n0;
		}else if (n1<n0){n1++;if (b[n1])c[i]=n1;}
		if (i==m&&(n0<nb||b[n1+1]))return ;
	}
	for (int i=1,ne=0;i<=m;i++){
		if (!c[i])ne=max(0,ne-1);
		else if (a[i])ne+=b[c[i]]-1;
		if (i==m&&ne) return ;
	}
	ll x1=1,n0=2,n1=nb-1;
	if (nb==0) n0--,n1++;
	for (int i=1;i<=nb;i++)if (b[i])n0+=2,n1+=b[i]*2-1;else n1++;
	for (int i=0;i<=(n+1)/2;i++){x1=x1*C(nb,f[i])%mo;nb-=f[i];}
	ans=(ans+x1*C(n+n0-1,n0+n1-1))%mo;
}
void fen(int x,int no){
	int ne=max(2,no*2);
	if (no>n+1)chk();
	else for (int i=0;i<=x/ne;i++){f[no]=i;fen(x-i*ne,no+1);}
}
int main(){
	read(n);read(m);
	jie[0]=1;for (int i=1;i<=200;i++)jie[i]=jie[i-1]*i%mo;
	nj[200]=po(jie[200],mo-2);for (int i=199;i>=0;i--)nj[i]=nj[i+1]*(i+1)%mo;
	for (int i=1;i<=m;i++){char ch=getchar();while (ch!='b'&&ch!='r')ch=getchar();a[i]=(ch=='b');}
	fen(n+1,0);
	cout<<ans<<endl;
	return 0;
}