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;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const LL mod = 1e9 + 7;
const int MC = 202;
LL fct[MC+1];
LL invfct[MC+1];
int N,K;
string s;
vector<int> V;
LL ans;

void build(){
	fct[0] = fct[1] = 1;
	repp(i,2,MC+1){
		fct[i] = fct[i-1] * i % mod;
	}
	LL x = fct[MC];
	invfct[MC] = 1;
	for(int i = mod - 2 ; i > 0 ; i >>= 1){
		if(i % 2 == 1) (invfct[MC] *= x) %= mod;
		(x *= x) %= mod;
	}
	repm(i,MC,0){
		invfct[i-1] = invfct[i] * i % mod;
	}
}

LL comb(int x , int y){
	if(x < 0 || y < 0) return 0;
	return invfct[x] * invfct[y] % mod * fct[x+y] % mod;
}

bool solve(int y , int z , int a , LL r , bool b){
	if(z > N+1 || a > N+1) return 0;
	if(b){
		int x = V.size();
		int itr = x - 1 , itb = x - 1;
		int p = y , q = 0;
		for(auto c : s){
			if(c=='r'){
				if(itr >= 0) --itr;
				else if(p>0) --p;
				else if(q) --q;
			} else {
				if(itb > itr){
					q += V[itb]-1;
					--itb;
				} else if(q) --q;
			}
		}
		if(~itr || ~itb || p || q) return 0;
		LL w = fct[x+y] * r % mod;
		w = w * comb(N-z+1,z+2*x) % mod;
		(ans += w) %= mod;
	}
	solve(y,z,a+1,r,0);
	V.PB(a);
	for(int i = 1 ; solve(y,z+2*a*i,a+1,r*invfct[i]%mod,1) ; ++i) V.PB(a);
	while(V.size() && *V.rbegin() == a) V.pop_back();
	return 1;
}

int main(){
	build();
	cin >> N >> K;
	cin >> s;
	for(int i = 0 ; solve(i,i*2,1,invfct[i],1) ; ++i);
	cout << ans << endl;
	return 0;
}