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 fo(i,a,b)for(int i=a,_e=b;i<=_e;++i)
#define fd(i,a,b)for(int i=b,_e=a;i>=_e;--i)
#define ll long long
using namespace std;
const int N=255,mo=1e9+7;
int n,k,ans,g,Ga,Gb;
int c[N][N],st[N];
char s[N];
void calc(){
	int ga=g,gb=g,tot=0;
	fo(i,1,k)
		if(s[i]=='r'&&ga)--ga;else
		if(s[i]=='b'&&gb>ga&&st[gb]>1)tot+=st[gb]-2,--gb;else
		if(tot)--tot;
	for(;st[gb]==1;)--gb;
	if(ga||gb||tot)return;
	tot=1;
	for(int i=1,j=0;i<=g;i=j+1){
		for(;j<g&&st[j+1]==st[i];)++j;
		tot=(ll)tot*c[j][j-i+1]%mo;
	}
	ga=Ga-1;gb=Gb+Ga;
	ans=((ll)tot*c[n-ga+gb][gb]+ans)%mo;
}
void find(int _n,int _k,int len){
	calc();
	++g;
	int la=Ga,lb=Gb;
	for(int i=len;_n+(i==1?2:i*2-2)<=n+1&&_k+i<=k;++i)
		Ga=la+(i==1?2:i*2-2),Gb=lb+(i>1)*2,st[g]=i,find(_n+(i==1?2:i*2-2),_k+i,i);
	--g;
}
int main(){
	scanf("%d%d\n%s",&n,&k,s+1);
	fo(i,0,250){
		c[i][0]=1;
		fo(j,1,i)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mo;
	}
	find(0,0,1);
	cout<<ans;
}