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>
const int MOD=1e9+7;
struct mint{int x;mint(int x=0):x(x){}};
inline mint operator+  (mint a,mint b){return a.x+b.x<MOD?a.x+b.x:a.x+b.x-MOD;}
inline mint operator-  (mint a){return MOD-a.x;}
inline mint operator-  (mint a,mint b){return a+-b;}
inline mint operator*  (mint a,mint b){return 1LL*a.x*b.x%MOD;}
inline mint operator<< (mint x,int y){mint r=1;for(;y;y>>=1,x=x*x)if(y&1)r=r*x;return r;}
inline mint operator~  (mint x){return x<<MOD-2;}
inline mint operator/  (mint a,mint b){return a*~b;}
inline mint&operator+= (mint&a,mint b){return a=a+b;}
inline mint&operator-= (mint&a,mint b){return a=a-b;}
inline mint&operator*= (mint&a,mint b){return a=a*b;}
inline mint&operator<<=(mint&x,int y){return x=x<<y;}
inline mint&operator/= (mint&a,mint b){return a=a/b;}
#define MN 141
char s[MN+5];
mint F[MN+5],R[MN+5],ans;
int n,a[MN+5],an,b[MN+5],bn,c[MN+5],u[MN+5],p[MN+5];
inline mint C(int n,int m){return F[n]*R[m]*R[n-m];}
void dfs(int x,int y,int z,int s0)
{
	int i,j,k;
	memset(u,0,sizeof(u));
	for(i=j=1;i<z;u[a[i++]]=1)if(p[z-i])
	{
		while(j<=bn&&b[j]<a[i])++j;
		if(j>bn)break;
		u[c[i]=b[j++]]=1;
	}
	if(i==z)for(i=j=1;i<z;++i)
	{
		for(k=1;k<p[z-i];++k)
		{
			while(s[j]&&(j<c[i]||u[j]))++j;
			if(!s[j++])break;
		}
		if(k<p[z-i])break;
	}
	if(i==z)
	{
		mint s=F[z-1];
		for(i=1;i<z;s*=R[j-i],i=j)for(j=i;j<z&&p[i]==p[j];++j);
		ans+=s*C(n+2*(z-1-s0),2*(z-1+x));
	}
	if(z<=an)for(;x+y<=an+bn-z&&x+y+s0+!y<=n/2;++y)dfs(x+y,p[z]=y,z+1,s0+!y);
}
int main()
{
	int m,i;
	scanf("%d%d%s",&n,&m,s+1);++n;
	for(F[0]=i=1;i<=MN;++i)F[i]=F[i-1]*i;
	for(R[i=MN]=~F[MN];i--;)R[i]=R[i+1]*(i+1);
	for(i=1;i<=m;++i)(s[i]=='r'?a[++an]:b[++bn])=i;
	dfs(0,0,1,0);
	printf("%d",ans);
}