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:
//Love and Freedom.
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define ll long long
#define inf 20021225
#define N 610
#define mdn 1000000007
using namespace std;
int read()
{
	int s=0,t=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')	t=-1; ch=getchar();}
	while(ch>='0' && ch<='9')	s=s*10+ch-'0',ch=getchar();
	return s*t;
}
int ksm(int bs,int mi)
{
	int ans=1;
	while(mi)
	{
		if(mi&1)	ans=1ll*ans*bs%mdn;
		bs=1ll*bs*bs%mdn; mi>>=1;
	}
	return ans;
}
void upd(int &x,int y){x+=x+y>=mdn?y-mdn:y;}
int fac[N],inv[N],a[N],ans,n,k,r[N],b[N];
char ch[N]; bool vis[N];
void init()
{
	fac[0]=1;
	for(int i=1;i<N;i++)	fac[i]=1ll*fac[i-1]*i%mdn;
	inv[N-1]=ksm(fac[N-1],mdn-2);
	for(int i=N-1;i;i--)	inv[i-1]=1ll*inv[i]*i%mdn;
}
int C(int n,int m){return n<m?0:1ll*fac[n]*inv[m]%mdn*inv[n-m]%mdn;}
int solve(int tot,int dat)
{
	int cur=fac[tot],cnt=0;
	for(int i=1;i<=tot;i++)
	{
		if(a[i]==a[i-1])	cnt++;
		else	cur=1ll*cur*inv[cnt]%mdn,cnt=1;
	}
	cur=1ll*cur*inv[cnt]%mdn;
	int pt=1; memset(vis,0,n+1);
	for(int i=1;i<=k;i++)	if(ch[i]=='r')
		if(pt<=tot)	r[pt]=i,pt++,vis[i]=1;
	if(pt<=tot)	return 0; pt=1;
	for(int i=1;i<=k;i++)	if(ch[i]=='b')
		if(pt<=tot&&r[pt]<i&&a[pt]>=2)	b[pt]=i,pt++,vis[i]=1;
	if(pt<=tot&&a[pt]>=2)	return 0; pt=1; int qwq=a[pt]-2;
	for(int i=1;i<=k;i++)	if(!vis[i])
		if(pt<=tot&&b[pt]<i&&qwq>0)
		{
			qwq--; if(!qwq)	pt++,qwq=a[pt]-2;
		}
	if(qwq>0)	return 0;
	return 1ll*dat*cur%mdn;
}
void dfs(int val,int x,int ful,int wei)
{
	if(ful<wei)	return;
	if(!val)	return upd(ans,solve(x-1,C(ful,wei)));
	for(int i=1;i<=min(val,a[x-1]);i++)	a[x]=i,dfs(val-i,x+1,ful+(i>=2?2:0),wei+2*i);
}
int main()
{
	n=read(),k=read(); init();
	scanf("%s",ch+1); a[0]=n+1; int flag=0,flag1=0;
	for(int i=2;i<=k;i++)	if(ch[i]=='b'&&ch[i-1]=='r')	flag=1;
	for(int i=1;i<=k;i++)	if(ch[i]=='r')	flag1=1;
	if(n==1)	return puts(!flag1?"1":flag?"3":"2"),0; 
	for(int i=1;i<=n;i++)	dfs(i,1,n+1,0);
	printf("%d\n",(ans+1)%mdn);
	return 0;
}