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<iostream>
#include<cstdio>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=1010,P=1e9+7;
int n,m,ans,cnt;
int a[N],b[N],c[N],d[N],f[N],p[N],fc[N],vf[N],iv[N];
char s[N];
void ini(int n){
	iv[1]=fc[0]=vf[0]=1;
	FOR(i,2,n) iv[i]=1ll*(P-P/i)*iv[P%i]%P;
	FOR(i,1,n) fc[i]=1ll*fc[i-1]*i%P,vf[i]=1ll*vf[i-1]*iv[i]%P;
}
int C(int x,int y){return x<y?0:1ll*fc[x]*vf[x-y]%P*vf[y]%P;}
void work(int L,int s,int t){
	int r=1;
	FOR(i,1,m) c[i]=0,b[i]=f[i];b[L+1]=0;
	//FOR(i,1,L) cout<<b[i]<<' ';cout<<'\n';
	FOR(i,1,m)if(!a[i] && r<=L) b[c[i]=r]--,p[r++]=i;
	if(b[r]) return;r=1;
	FOR(i,1,m)if( a[i] && b[r] && p[r]<i) b[c[i]=r]--,p[r++]=i;
	if(b[r]) return;r=1;
	FOR(i,1,m)if(!c[i] && b[r] && p[r]<i && !--b[r]) r++;
	if(b[r]) return;
	int ret=fc[L];
	FOR(i,1,m) ret=1ll*ret*vf[d[i]]%P;
	(ans+=1ll*ret*C(t,2*s)%P)%=P;
}
void dfs(int x,int s,int t){
	if(t<2*s) return;work(x-1,s,t);
	FOR(i,1,min(f[x-1],m-s)) f[x]=i,d[i]++,dfs(x+1,s+i,t+2*(i>=2)),d[i]--;
}
int main(){
	//freopen("1.in","r",stdin);
	scanf("%d%d%s",&n,&m,s+1);ini(1000);
	FOR(i,1,m) a[i]=s[i]=='b';
	f[0]=m;dfs(1,0,n+1);
	cout<<ans<<'\n';
}