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 <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long ll;

const int N=255,Mo=1e9+7;

int n,k,t,f[N],C[N][N],ans;
char st[N];

void pre(int N) {
	fo(i,0,N) {
		C[i][0]=1;
		fo(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mo;
	}
}

void calc() {
	int sum=0,tr=t,tb=t;
	fo(i,1,k) {
		if (st[i]=='r'&&tr) tr--;
		else if (st[i]=='b'&&f[tb]>1&&tb>tr) sum+=f[tb]-2,tb--;
		else if (sum) sum--;
	}
	while (f[tb]==1) tb--;
	if (tr||tb||sum) return;

	int ret=1;
	for(int l=1,r=0;l<=t;l=r+1) {
		while (r<t&&f[r+1]==f[l]) r++;
		ret=(ll)ret*C[r][r-l+1]%Mo;
	}

	int cnt=0,ulm=0;
	fo(i,1,t) {
		cnt+=(f[i]==1?1:f[i]*2-3)+1;
		ulm+=(f[i]==1?1:f[i]*2-3)+1;
		ulm+=2*(f[i]>1);
	}
	cnt--;ulm++;
	(ans+=(ll)ret*C[n-cnt+ulm-1][ulm-1]%Mo)%=Mo;
	//fo(i,1,t) printf("%d ",f[i]);printf("%d\n",ans);
}

void dfs(int x,int y,int la) {
	calc();
	++t;
	if (la==1&&x+2<=n+1&&y+1<=k) {
		f[t]=1;
		dfs(x+2,y+1,1);
	}
	for(int i=max(la,2);;i++) {
		if (y+i>k) break;
		if (x+2*i-2>n+1) break;
		f[t]=i;
		dfs(x+2*i-2,y+i,i);
	}
	t--;
}

int main() {
	scanf("%d%d",&n,&k);
	pre(250);
	scanf("%s",st+1);
	dfs(0,0,1);
	printf("%d\n",ans);
	return 0;
}