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:
//我永远喜欢ysgh
#include<bits/stdc++.h>
#define For(i,x,y) for (register int i=(x);i<=(y);i++)
#define FOR(i,x,y) for (register int i=(x);i<(y);i++)
#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fil(a,b) memset((a),(b),sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pa;
typedef vector<int> poly;
inline ll read(){
    ll x=0,f=1;char c=getchar();
    while ((c<'0'||c>'9')&&(c!='-')) c=getchar();
    if (c=='-') f=-1,c=getchar();
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

const int N = 110;
int n,k;
char s[N];

const int mod = 1e9+7;
int fac[N<<1],ifac[N<<1];
inline void init(){
	fac[0]=1;
	For(i,1,200) fac[i]=1ll*fac[i-1]*i%mod;
	auto power=[](int a,int b){
		int ret=1;
		for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) ret=1ll*ret*a%mod;
		return ret;
	};
	ifac[200]=power(fac[200],mod-2);
	Dow(i,199,0) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}

int ans,cnt,a[N],_cnt,_a[N],tot;
inline bool check(){
	if (!_cnt) return 0;
	cnt=_cnt;
	For(i,1,cnt) a[i]=_a[i];
	reverse(a+1,a+1+cnt);
	int lim=0;
	while (lim<cnt&&a[lim+1]>1) ++lim;
	int cnt_r=0,cnt_b=0,cnt_x=0;
	For(i,1,k) 
		if (s[i]=='r'&&cnt_r<cnt) ++cnt_r;
		else if (s[i]=='b'&&cnt_b<min(lim,cnt_r)) ++cnt_b,cnt_x+=a[cnt_b]-2;
		else if (cnt_x) --cnt_x;
	return !cnt_x&&cnt_b==lim&&cnt_r==cnt;
}
inline int calc(int sum){
	auto C=[=](int n,int m){
		return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
	};
	int ret=fac[cnt];
	for (int l=1,r=1;l<=cnt;l=++r){
		while (a[r+1]==a[l]&&r<cnt) ++r;
		ret=1ll*ret*ifac[r-l+1]%mod;
	}
	return 1ll*ret*C(n+tot-1,sum+tot-1)%mod;
}
inline void dfs(int sum,int last){
	if (check()){
		ans+=calc(sum-1);
		if (ans>=mod) ans-=mod;
	}
	if (last==1&&sum+1<=n) _a[++_cnt]=1,dfs(sum+2,1),--_cnt;
	for (int i=last;sum+i*2-3<=n;i++){
		if (i==1) continue;
		_a[++_cnt]=i,tot+=2;
		dfs(sum+i*2-2,i);
		--_cnt,tot-=2;
	}
}

int main(){
	n=read(),k=read(),scanf("%s",s+1);
	init(),tot=2,ans=1,dfs(0,1),printf("%d\n",ans);
}