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<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 1005
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll ans;
int n,k;
char s[maxn];
int f[maxn];
ll c[maxn][maxn],fac[maxn],inv[maxn];
ll quickpow(ll p,ll k)
{
	ll res=1;
	while(k)
	{
		if(k&1)
			res=(res*p)%mod;
		p=(p*p)%mod;
		k>>=1;
	}
	return res;
}
void check(int len,int low)
{
	int cnt1=0,cnt2=0,temp1=0,temp2=0;
	for(int i=1;i<=k;i++)
	{
		if(s[i]=='r' && cnt1<len)
		{
			cnt1++;
			temp1+=(f[cnt1]!=1);
		}
		else if(s[i]=='b' && temp1)
		{
			temp1--;
			cnt2++;
			temp2+=(f[cnt2]-2);
		}
		else if(temp2)
			temp2--;
	}

//	cerr<<len<<" "<<cnt1<<" "<<temp1<<" "<<temp2<<endl;
	if(cnt1<len || temp1 || temp2)
		return;

//	cerr<<"+1"<<endl;

	ll res=fac[len];
	for(int i=1;i<=len;i++)
	{
		int j=i;
		while(f[j+1]==f[i] && j<len) j++;
		res=(res*inv[j-i+1])%mod;
		i=j;
	}
//	cerr<<"+2"<<endl;
	ll sz=len+1;
	for(int i=1;i<=len;i++)
		sz+=(f[i]*2-1);

//	cerr<<len<<" "<<n<<' '<<sz<<" "<<low<<" "<<n-(low-sz+1)<<endl;

	ans+=(res*c[n-low+sz-1][sz-1])%mod;
	ans%=mod;
}
void dfs(int now,int len,int low)
{
//	cerr<<now<<" "<<len<<" "<<low<<endl;
	if(low>n) return;
//	cerr<<now<<" "<<len<<" "<<low<<endl;
	check(len-1,low);
	for(int i=now;i>=1;i--)
	{
		f[len]=i;
		dfs(i,len+1,low+(max(2*i-3,1))+(len!=1));
	}
}
int main()
{
	scanf("%d%d%s",&n,&k,s+1);
	for(int i=0;i<=300;i++)
	{
		c[i][0]=c[i][i]=1;
		for(int j=1;j<=i-1;j++)
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	}
	inv[0]=fac[0]=1;
	for(int i=1;i<=300;i++)
		fac[i]=(fac[i-1]*i)%mod,inv[i]=(quickpow(fac[i],mod-2));
	dfs(70,1,0);
	printf("%lld\n",ans);
}