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>
using namespace std;

typedef long long ll;
const int maxn=70+10,mod=1e9+7;
int n,k,cnt[maxn],a[maxn],m,beg[maxn];
char s[maxn];
bool vis[maxn];
ll ans,fac[maxn],inv[maxn],c[maxn*10][maxn*10];

inline ll qpow(ll a,ll n){
	ll res=1;
	while(n){
		if(n&1ll)
			res=res*a%mod;
		a=a*a%mod;
		n>>=1;
	}
	return res;
}
void init(){
	fac[0]=1;
	for(int i=1;i<maxn;++i)
		fac[i]=fac[i-1]*i%mod;
	inv[maxn-1]=qpow(fac[maxn-1],mod-2);
	for(int i=maxn-1;i;--i)
		inv[i-1]=inv[i]*i%mod;
	for(int i=0;i<maxn*10;++i){
		c[i][0]=1;
		for(int j=1;j<=i;++j)
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	}
}
void judge(int rest){
	m=0;
	for(int i=n;~i;--i)
		for(int j=0;j<cnt[i];++j)
			a[m++]=i;
	if(m==0){
		ans=(ans+1)%mod;
		return;
	}
	memset(vis,0,sizeof(vis));
	for(int i=0,j=0;i<m;++i){
		while(j<k&&s[j]=='b')
			++j;
		if(j==k)
			return;
		vis[j]=true;
		beg[i]=++j;
	}
	for(int i=0,j=0;i<m&&a[i]>=1;++i){
		if(j<beg[i])j=beg[i];
		while(j<k&&(s[j]=='r'||vis[j]))
			++j;
		if(j==k)
			return;
		vis[j]=true;
		beg[i]=++j;
	}
	for(int i=0,j=0;i<m&&a[i]>=2;++i){
		if(j<beg[i])j=beg[i];
		int rest=a[i]-1;
		while(rest){
			while(j<k&&vis[j])
				++j;
			if(j==k)
				break;
			else
				vis[j]=true,--rest;
		}
		if(rest)
			return;
		++j;
	}
	ll res=fac[m];
	for(int i=0;i<=n;++i)
		res=res*inv[cnt[i]]%mod;
	int box=1;
	for(int i=0;i<m;++i)
		if(a[i])
			box+=2*a[i]+2;
		else
			box+=2;
	res=res*c[box+rest-1][rest]%mod;
	ans=(ans+res)%mod;
}
void dfs(int pos,int rest){
	if(!pos){
		for(int i=0;i*2<=rest;++i){
			cnt[0]=i;
			judge(rest-i*2);
		}
		return;
	}
	for(int i=0;i*2*pos<=rest;++i)
		cnt[pos]=i,dfs(pos-1,rest-i*2*pos);
}

int main(){
	init();
	cin>>n>>k>>s;
	dfs(n,n+1);
	cout<<ans<<endl;
	return 0;
}