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:
// This amazing code is by Eric Sunli Chen.
#include<bits/stdc++.h>
using namespace std;
template<typename T> bool get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'&&t!=EOF; t=getchar());
	if(t=='-')neg=true,t=getchar();if(t==EOF)return false;
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;return true;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) (get1(a)&&get1(b))
#define get3(a,b,c) (get1(a)&&get2(b,c))
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

const int mod=1e9+7;

int n,k,comb[233][233],tot,tot2,ma[111],mb[111];
char s[111];

int c[111],ans,use[111];
void dfs(int mx,int cnt,int sum,int coef)
{
	if(cnt+sum-1>n)return;
	if(cnt>tot)return;
	if(mx==0)
	{
		if(cnt==0)
		{
			ans++;if(ans>=mod)ans-=mod;
			return;
		}
		if(cnt-c[1]>tot2)return;
		
		bool ok=1;int cur=0;
		memset(use,0,sizeof(use));
		for(int i=(n+3)>>1;i>0;i--)
		{
			for(int j=1;j<=c[i];j++)
			{
				cur++;
				use[ma[cur]]=1;
				use[mb[cur]]=i-1;
			}
		}
		cur=0;
		for(int i=k;i>=1&&ok;i--)
		{
			cur++;
			if(cur<use[i])ok=0;
			else cur-=use[i];
		}
		if(ok)
		{
			int have=n-cnt-sum+1,need=sum+cnt+1+(cnt-c[1])*2;
			ans=(ans+1ll*coef*comb[have+need-1][need-1])%mod;
		}
		return;
	}
	for(c[mx]=0;c[mx]<=n;c[mx]++)dfs(mx-1,cnt+c[mx],sum+c[mx]*(mx==1?1:mx+mx-3),coef*1ll*comb[cnt+c[mx]][cnt]%mod);
}

int main()
{
	for(int i=0;i<233;i++)
	{
		comb[i][0]=1;
		for(int j=1;j<=i;j++)
		{
			comb[i][j]=comb[i-1][j]+comb[i-1][j-1];
			if(comb[i][j]>=mod)comb[i][j]-=mod;
		}
	}
	get2(n,k);
	scanf("%s",s+1);
	for(int i=1;i<=k;i++)if(s[i]=='r')
	{
		int j=i;
		for(;j<=k;j++)if(s[j]=='b'&&!use[j])break;
		tot++;tot2+=(j<=k);
		ma[tot]=i;mb[tot]=j;
		use[j]=1;
	}
	dfs((n+3)/2,0,0,1);
	printendl(ans);
	return 0;
}