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;
typedef long long ll;
const int N=220,p=1000000007;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int qpow(int x,int k){
	int t=1;
	for (;k;k>>=1){
		if (k&1) t=(ll)t*x%p;
		x=(ll)x*x%p;
	}
	return t;
}
int n,m,ans,a[N],s[N],pos[N],C[N][N],po[N],inv[N];
char ch[N];bool h[N];
int get_nex(char c,int i){
	for (;(i<=m)&&(h[i]||(ch[i]!=c));i++);
	return i;
}
int get_n(int i){
	for (;(i<=m)&&h[i];i++);
	return i;
}
bool check(int dep){
	memset(h,0,m+1);
	for (int i=1;i<=dep;i++){
		pos[i]=get_nex('r',1);
		if (pos[i]>m) return false;
		h[pos[i]]=1;
	}
	for (int i=1;i<=dep;i++)
	if (a[i]>1){
		pos[i]=get_nex('b',pos[i]+1);
		if (pos[i]>m) return false;
		h[pos[i]]=1;
	}
	for (int i=1;i<=dep;i++)
	for (int j=3;j<=a[i];j++){
		pos[i]=get_n(pos[i]+1);
		if (pos[i]>m) return false;
		h[pos[i]]=1;
	}
	return true;
}
void calc(int res,int r,int dep){
	int t=po[dep-1],s1=n+1,s2=0;
	for (int i=1;i<=min(n+1,m);i++){
		t=(ll)t*inv[s[i]]%p;
		s1+=(i>1)*2*s[i];
		s2+=2*s[i]*i;
	}
	if ((s1<s2)||(!check(dep-1))) return;
	ans=(ans+(ll)t*C[s1][s2])%p;
	for (int i=1;i<=r;i++){
		a[dep]=i;s[i]++;
		calc(res-i,min(i,res-i),dep+1);
		s[i]--;
	}
	a[dep]=0;
}
int main(){
	n=read();m=read();
	scanf(" %s",ch+1);
	C[0][0]=po[0]=inv[0]=1;
	for (int i=1;i<=214;i++){
		C[i][0]=1;po[i]=(ll)po[i-1]*i%p;
		inv[i]=qpow(po[i],p-2);
		for (int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
	}
	calc(min(n+1,m),min(n+1,m),1);
	printf("%d\n",ans);
	return 0;
}