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>
using namespace std;
const int mod=1000000007;
inline void add(int &x,int y){(x+=y)>=mod?x-=mod:0;}
inline int pl(int x,int y){return (x+=y)>=mod?x-mod:x;}
inline int kpow(int a,int b)
{
	int s=1;
	for(;b;b>>=1,a=1ll*a*a%mod)
		if(b&1)s=1ll*s*a%mod;
	return s;
}
int C[310][310],jc[310],jcv[310];
int n,k,ans;
char s[100];
int p[100],pos[100];
bool used[100];
int CNT;
void calc(int m)
{
	++CNT;
//	printf("%d:",m);
//	for(int i=1;i<=m;++i)printf("%d ",p[i]);printf("\n");
	memset(used+1,0,n);
	for(int i=1,last=1;i<=m;++i)
	{
		while(last<=k&&s[last]!='r')++last;
		if(last>k)return;
		pos[i]=last;used[last]=1;++last;
	}
	for(int i=1,last=1;i<=m;++i)
		if(p[i]>=2)
		{
			if(last<=pos[i])last=pos[i]+1;
			while(last<=k&&s[last]!='b')++last;
			if(last>k)return;
			pos[i]=last;used[last]=1;++last;
		}
	for(int i=1,last=1;i<=m;++i)
		if(p[i]>2)
		{
			if(last<=pos[i])last=pos[i]+1;
			int d=p[i]-2;
			while(d)
			{
				while(last<=k&&used[last])++last;
				if(last>k)return;
				--d;++last;
			}			
		}
	int res=jc[m],up=n-m+1,dn=m+1;
	for(int i=1,r;i<=m;i=r+1)
	{
		r=i;
		while(r<m&&p[r+1]==p[i])++r;
		res=1ll*res*jcv[r-i+1]%mod;
	}
	for(int i=1;i<=m;++i)up-=p[i]==1?1:2*p[i]-3,dn+=2*p[i]-1;
	res=1ll*res*C[up+dn-1][dn-1]%mod;
	add(ans,res);
//	printf("%d:",m);
//	for(int i=1;i<=m;++i)printf("%d ",p[i]);printf("\n");
//	printf("%d %d %d\n",up,dn,res);
}
void dfs(int w,int res,int last,int sum)
{
	calc(w-1);
//	printf("%d %d %d\n",w,res,last);
	if(!res)return;
	for(int i=min(last,res);i;--i)
		if(sum+1+(i==1?1:2*i-3)<=n)p[w]=i,dfs(w+1,res-i,i,sum+1+(i==1?1:2*i-3));
}
int main()
{
	for(int i=0;i<=300;++i)
	{
		C[i][0]=1;
		for(int j=1;j<=i;++j)C[i][j]=pl(C[i-1][j-1],C[i-1][j]);
	}
	jc[0]=1;
	for(int i=1;i<=300;++i)jc[i]=1ll*jc[i-1]*i%mod;
	jcv[300]=kpow(jc[300],mod-2);
	for(int i=300;i;--i)jcv[i-1]=1ll*jcv[i]*i%mod;
	scanf("%d %d",&n,&k);
	scanf("%s",s+1);
	dfs(1,k,k,-1);
	printf("%d",ans);
//	printf("\n%d",CNT);
	return 0;
}