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<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;

#define int long long

#define left __left__

const int N=70+10;

const int A=520;

const int MOD=1000000007;

int n,k;

char s[N];

int C[A][A];

void prework()
{
	int i,j;
	for(i=0;i<A;++i)
	{
		C[i][0]=1;
		for(j=1;j<=i;++j)
			if((C[i][j]=C[i-1][j-1]+C[i-1][j])>=MOD)
				C[i][j]-=MOD;
	}
}

int ans;

int B[N],ed,left;

bool valid()
{
	if(!ed)
		return false;
	int i,j=1,jj=1,c=0;
	for(i=1;i<=k&&(j<=ed||B[jj]>1||c);++i)
	{
		if(j<=ed&&s[i]=='r')
			++j;
		else if(jj<j&&B[jj]>1&&s[i]=='b')
			c+=B[jj++]-2;
		else if(c)
			--c;
	}
	return !(j<=ed||B[jj]>1||c);
}

void update()
{
	int i,j,res(1),em(0);
	for(i=1;i<=ed;i=j+1)
	{
		for(j=i;B[j+1]==B[i];++j);
		res=res*C[j][i-1]%MOD;
		em+=(j-i+1)*((B[i]<<1)-1);
	}
	em+=ed+1;
	res=res*C[em-1+left][em-1]%MOD;
	if((ans+=res)>=MOD)
		ans-=MOD;
}

void dfs(int lim)
{
	if(left<0)
		return;
	if(valid())
		update();
	if(ed)
		--left;
	++ed;--left;
	dfs(B[ed]=1);
	++left;
	for(int i=2;i<=lim;++i)
	{
		left-=(i<<1)-3;
		dfs(B[ed]=i);
		left+=(i<<1)-3;
	}
	B[ed--]=0;
	if(ed)
		++left;
}

signed main()
{
	scanf("%lld%lld%s",&n,&k,s+1);
	prework();
	left=n;dfs(233);
	printf("%lld",(ans+1)%MOD);
	return 0;
}