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 p=1000000007;
 
int c[300][300],g[100],h[100];
char b[100];
int i,j,k,l,m,n,r,s,t;
 
inline void pre()
{
	scanf("%d%d",&n,&m);
	scanf("%s",b+1);
	for (i=0;i<=250;i++)
		for (j=0;j<=i;j++)
			if ((j==0) || (j==i))
				c[i][j]=1;
			else
				c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
	return;
}
 
inline void calc()
{
	for (i=1;i<=n;i++)
		h[i]=g[i];
	t=0;
	for (i=1,k=1,l=1;i<=m;i++)
		if ((b[i]=='r') && (h[k]>0))
			h[k]--,k++;
		else
		if ((b[i]=='b') && (h[l]>0) && (l<k))
			h[l]--,t=t+h[l],l++;
		else
		if (t>0)
			t--;
	if ((h[k]) || (h[l]) || (t))
		return;
	r=1;
	for (i=1;g[i];i=j)
	{
		for (j=i;g[i]==g[j];j++);
		r=1LL*r*c[j-1][i-1]%p;
		if (g[i]==1)
			t=t+j-i;
		else
			t=t+(j-i)*(2*g[i]-3);
	}
	t=t+k-2;
	if (n-t<0)
		return;
	s=(s+1LL*r*c[n+2*l-1][t+2*l-1])%p;
	return;
}
 
inline void dfs(int w,int x,int y,int z)
{
	if (w<0)
		return;
	if (z)
		calc();
	if (x)
	{
		g[z+1]=1,dfs(w-2,x-1,1,z+1);
		for (int i=2;(i<=x) && (i<=y);i++)
			g[z+1]=i,dfs(w-2*i+2,x-i,i,z+1);
		g[z+1]=0;
	}
	return;
}
 
int main()
{
	pre();
	dfs(n+1,m,m,0);
	printf("%d",(s+1)%p);
	return 0;
}