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;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 300;
const int mod = 1e9 + 7;

int n, k;
string str;
lint fact[MAXN], invf[MAXN];

lint ipow(int x, int p){
	lint ret = 1, piv = x;
	while(p){
		if(p & 1) ret = ret * piv % mod;
		piv = piv * piv % mod;
		p >>= 1;
	}
	return ret;
}

lint bino(int x, int y){
	if(x < y) return 0;
	return fact[x] * (invf[y] * invf[x-y] % mod) % mod;
}

int f(int x){ return 2 * max(x - 1, 1); }

int solve(vector<int> v){
	int sum = 0;
	int ptr = 0;
	reverse(v.begin(), v.end());
	queue<int> que;
	for(auto &i : str){
		if(i == 'r'){
			if(ptr < v.size()){
				if(v[ptr] > 1){
					que.push(v[ptr] - 2);
				}
				ptr++;
			}
			else{
				if(sum) sum--;
			}
		}
		if(i == 'b'){
			if(!que.empty()){
				sum += que.front();
				que.pop();
			}
			else if(sum) sum--;
		}
	}
	if(ptr != v.size() || sum || que.size()) return 0;
	if(v.empty()) return 1;
	lint ret = fact[v.size()];
	for(int i=0; i<v.size(); ){
		int e = i;
		while(e < v.size() && v[i] == v[e]) e++;
		ret *= invf[e - i];
		ret %= mod;
		i = e;
	}
	{
		int canZero = 2;
		int canAny = v.size() + 1;
		for(int i=0; i<v.size(); i++){
			canAny += 2 * v[i] - 1;
			canZero += (v[i] > 1) * 2;
		}
		ret *= bino(n + canZero - 1, canAny - 1);
	}
	return ret % mod;
}

vector<vector<int> > canon;

void dfs(int x, int l, vector<int> v){
	canon.push_back(v);
	for(int i=l; x + f(i) <= n; i++){
		v.push_back(i);
		dfs(x + f(i), i, v);
		v.pop_back();
	}
}

int main(){
	fact[0] = invf[0] = 1;
	for(int i=1; i<MAXN; i++){
		fact[i] = fact[i-1] * i % mod;
		invf[i] = ipow(fact[i], mod - 2);
	}
	cin >> n >> k >> str;
	vector<int> v;
	dfs(-1, 1, v);
	lint ret = 0;
	for(auto &i : canon){
		ret += solve(i);
	}
	cout << ret % mod << endl;
}