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<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int Mod=1000000007;
int n,k;
char s[110];
bool vis[110];
bool book[110];
int a[110];
bool check(int m)
{
	memset(vis,0,sizeof(vis));
	memset(book,0,sizeof(book));
	int cnt=0;
	for(int i=1;i<=m&&a[i]==1;i++)cnt++;
	int nowr=1,nowb=1;
	for(int i=1;i<=m-cnt;i++)
	{
		while(nowr<=k&&(vis[nowr]||s[nowr]!='r'))nowr++;
		while(nowb<=k&&(vis[nowb]||s[nowb]!='b'||nowb<=nowr))nowb++;
		if(nowr>k||nowb>k)return false;
		vis[nowr]=true;
		vis[nowb]=true;
		book[nowb]=true;
	}
	int tmp=cnt;
	for(int i=1;i<=k&&tmp;i++)
		if(!vis[i]&&s[i]=='r'){
			vis[i]=true;
			tmp--;
		}
	if(tmp)return false;
	int now=cnt+1,num=0;
	for(int i=k;now<=m;i--)
	{
		if(!vis[i])num++;
		if(book[i]){
			num-=a[now]-2;
			if(num<0)return false;
			now++;
		}
	}
	return true;
}
int fpow(int a,int b)
{
	int ans=1,t=a;
	while(b)
	{
		if(b&1)ans=1ll*ans*t%Mod;
		t=1ll*t*t%Mod;
		b>>=1;
	}
	return ans;
}
int ans;
int fac[2010],inv[2010];
void init()
{
	int N=2000;
	fac[0]=1;
	for(int i=1;i<=N;i++)
		fac[i]=1ll*fac[i-1]*i%Mod;
	inv[N]=fpow(fac[N],Mod-2);
	for(int i=N;i>=1;i--)
		inv[i-1]=1ll*inv[i]*i%Mod;
	return ;
}
int C(int x,int y)
{
	if(x<0||y<0||x-y<0)return 0;
	return 1ll*fac[x]*inv[y]%Mod*inv[x-y]%Mod;
}
void solve(int m,int len)
{
	int s=m+1;//block-1
	for(int i=1;i<=m;i++)
		if(a[i]==1)s++;
		else s+=(a[i]-1)*2+1;
	int res=1ll*C(n-len+s-1,s-1)*fac[m]%Mod;
	for(int i=1,j;i<=m;i=j)
	{
		j=i;
		while(j<=m&&a[j]==a[i])j++;
		res=1ll*res*inv[j-i]%Mod;
	}
	ans=(ans+res)%Mod;
	return ;
}
int cntr;
bool dfs(int m,int lst,int sum,int len)
{
	if(!check(m-1))return false;
	if(m-1>cntr)return true;
	solve(m-1,len);
	for(a[m]=lst;a[m]<=k-sum;a[m]++)
	{
		int tlen=len;
		if(m>1)tlen++;
		if(a[m]==1)tlen++;
		else tlen+=(a[m]-1)*2-1;
		if(tlen>n)break;
		if(!dfs(m+1,a[m],sum+a[m],tlen))
			break;
	}
	return true;
}
int main()
{
	init();
	scanf("%d %d",&n,&k);
	scanf("%s",s+1);
	for(int i=1;i<=k;i++)
		if(s[i]=='r')cntr++;
	dfs(1,1,0,0);
	printf("%d\n",ans);
	return 0;
}