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 <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define add(a,b) a=((a)+(b))%1000000007
#define min(a,b) (a<b?a:b)
#define mod 1000000007
#define Mod 1000000005
#define ll long long
#define N 1000
//#define file
using namespace std;

ll f[71][71][72],jc[N+1],Jc[N+1],ans;
int d[71],n,m,i,j,k,l,x,y;
char a[71];
bool bz[71];

ll qpower(ll a,int b) {ll ans=1; while (b) {if (b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;} return ans;};
ll C(int n,int m) {if (n<m) return 0;return jc[n]*Jc[m]%mod*Jc[n-m]%mod;}

int main()
{
	#ifdef file
	freopen("arc089F.in","r",stdin);
//	freopen("a.out","w",stdout);
	#endif
	
	jc[0]=1;
	fo(i,1,N) jc[i]=jc[i-1]*i%mod;
	Jc[N]=qpower(jc[N],Mod);
	fd(i,N-1,0) Jc[i]=Jc[i+1]*(i+1)%mod;
	
	scanf("%d%d",&n,&m);
	scanf("%s",a+1);
	ans=1;
	fo(x,0,n)
	{
		fo(y,0,n)
		if (x || y)
		{
			memset(bz,0,sizeof(bz)),k=l=0;
			fo(i,1,x)
			{
				fo(j,1,m) if (!bz[j] && a[j]=='r') break;
				fo(k,j,m) if (!bz[k] && a[k]=='b') break;
				if (k>m) break;
				bz[j]=bz[k]=1;
			}
			if (k>m) continue;
			fo(i,1,m) if (l<y && !bz[i] && a[i]=='r') ++l,bz[i]=1;
			if (l<y) continue;
			
			l=0;
			fd(j,m,1)
			if (bz[j] && a[j]=='b')
			{
				d[++l]=0;
				fo(k,j,m) d[l]+=!bz[k];
			}
			
			memset(f,0,sizeof(f)),f[0][0][0]=1;
			fo(i,0,x-1)
			{
				fo(j,0,d[x])
				{
					fo(k,0,d[x])
					if (f[i][j][k])
					{
						if (k<d[x]) add(f[i][j][k+1],f[i][j][k]);
						fo(l,1,x-i)
						if (j+l*k<=d[i+l])
						add(f[i+l][j+l*k][k+1],f[i][j][k]*C(i+l+y,l));
						else break;
					}
				}
			}
			
			fo(j,0,d[x])
			{
				fo(k,0,d[x]+1)
				{
					fo(l,0,n)
					add(ans,f[x][j][k]*C(l+(y+2*j+x*3)-1,(y+2*j+x*3)-1)%mod*C(n-(x+y-1)-2*j-l,x+y));
				}
			}
		}
	}
	printf("%lld\n",ans);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}