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 ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
ll num[71][71];
ll fact[10001];
ll inv_fact[10001];
ll mod_pow(ll a, ll b) {
	if (b == 0) return 1;
	if (b % 2 == 0) {
		ll x = mod_pow(a, b / 2);
		return (x*x) % MOD;
	}
	return (a*mod_pow(a, b - 1)) % MOD;
}
ll comb(ll n, ll k) {
	if (n < k) return 0;
	ll ret = fact[n];
	(ret *= inv_fact[k]) %= MOD;
	(ret *= inv_fact[n - k]) %= MOD;
	return ret;
}
int N, K;
ll ans;
string s;
bool check(vector<int> &v) {
	bool used[70] = {};
	int pos[70];
	int now= 0;
	for (int i = 0; i < v.size(); i++) {
		while (now < s.size()) {
			if (s[now] == 'r') break;
			now++;
		}
		if (now == s.size()) return 0;
		used[now] = 1;
		pos[i] = now;
		now++;
	}
	for (int i = 0; i < v.size(); i++) {
		if (v[i] == 1) break;
		now = pos[i] + 1;
		while (now < s.size()) {
			if (!used[now] && s[now] == 'b') break;
			now++;
		}
		if (now == s.size()) return 0;
		used[now] = 1;
		pos[i] = now;
	}
	for (int i = 0; i < v.size(); i++) {
		if (v[i] <= 2) break;
		int cnt = 0;
		now = pos[i] + 1;
		while (now < s.size()) {
			if (!used[now]) {
				used[now] = 1;
				cnt++;
			}
			if (cnt >= v[i] - 2) break;
			now++;
 		}
		if (now == s.size()) return 0;
	}
	return 1;
}
ll calc(vector<int> &v) {
	map<int, int> freq;
	for (int i = 0; i < v.size(); i++) {
		freq[v[i]]++;
	}
	ll ret = fact[v.size()];
	for (auto p : freq) {
		(ret *= inv_fact[p.second]) %= MOD;
	}
	int x = N + 1;
	int y = 0;
	for (int i = 0; i < v.size(); i++) {
		if (v[i] >= 2) x += 2;
		y += 2 * v[i];
	}
	(ret *= comb(x, y)) %= MOD;
	return ret;
}
void brute(int k, int prev, int sum, vector<int> &v) {
	if (sum > N) return;
	if (check(v)) {
		(ans += calc(v)) %= MOD;
	}
	for (int i = min(k, prev); i >= 1; i--) {
		int m = 1;
		if (i > 1) m = i * 2 - 3;
		if (v.size() > 0) m++;
		v.push_back(i);
		brute(k - i, i, sum + m, v);
		v.pop_back();
	}
}
int main() {
	fact[0] = inv_fact[0] = 1;
	for (int i = 1; i <= 10000; i++) {
		fact[i] = (fact[i - 1] * i) % MOD;
		inv_fact[i] = (inv_fact[i - 1] * mod_pow(i, MOD - 2)) % MOD;
	}
	cin >> N >> K;
	cin >> s;
	vector<int> v;
	brute(K, K, 0, v);
	cout << ans << endl;
}