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>
using namespace std;
#define N 142
#define mod 1000000007
int n,m,st[N],c[N][N],as,fr[N];
char s[N];
int pw(int a,int p){int as=1;while(p){if(p&1)as=1ll*as*a%mod;a=1ll*a*a%mod;p>>=1;}return as;}
int solve(int k)
{
	int v1=0,v3=k,v2=k;
	for(int i=1;i<=m;i++)
	if(s[i]=='r')
	if(v3>0)v3--;
	else v1-=v1>0;
	else if(v2>v3&&st[v2]>1)v1+=st[v2]-2,v2--;
	else v1-=v1>0;
	if(st[v2]>1||v3||v1)return 0;
	int ls=1,v5=fr[k];
	for(int i=2;i<=k;i++)if(st[i]==st[i-1])ls++;
	else v5=1ll*pw(fr[ls],mod-2)*v5%mod,ls=1;
	v5=1ll*pw(fr[ls],mod-2)*v5%mod;
	int s1=n+1,s2=1;
	for(int i=1;i<=k;i++)s1-=2*st[i]-2*(st[i]>1),s2+=2*st[i];
	if(s1<0)return 0;
	return 1ll*v5*c[s1+s2-1][s2-1]%mod;
}
void dfs(int d,int su)
{
	if(su<=35)as=(as+solve(d-1))%mod;else return;
	for(int i=st[d-1];i<=36-su;i++)st[d]=i,dfs(d+1,su+i-(i>1));
}
int main(){scanf("%d%d%s",&n,&m,s+1);for(int i=0;i<=141;i++)c[i][0]=c[i][i]=1;for(int i=2;i<=141;i++)for(int j=1;j<i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;fr[0]=1;for(int i=1;i<=70;i++)fr[i]=1ll*fr[i-1]*i%mod;st[0]=1;dfs(1,0);printf("%d\n",as);}