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;

const int P = 1000000007;
int fac[150], ifac[150], ans, n, k;
bool del[75];
vector<int> f, r;
char s[75];

int power(int a, int x) {
	int ans = 1;
	for (; x; x >>= 1, a = 1ll * a * a % P)
		if (x & 1) ans = 1ll * ans * a % P;
	return ans;
}

bool check() {
	fill(del + 1, del + 1 + k, false);
	for (int i = 0; i < f.size(); ++i) del[r[i]] = true;
	vector<int> b(f.size());
	for (int i = f.size() - 1; i >= 0; --i)
		if (f[i] >= 2) {
			int j;
			for (j = r[f.size() - 1 - i] + 1; (del[j] || s[j] == 'r') && j <= k; ++j);
			if (j > k) return false;
			b[i] = j;
			del[j] = true;
		}
	for (int i = f.size() - 1; i >= 0; --i)
		if (f[i] >= 3) {
			int cnt = f[i] - 2;
			for (int j = b[i] + 1; cnt && j <= k; ++j)
				if (!del[j]) del[j] = true, --cnt;
			if (cnt) return false;
		}
	return true;
}

void dfs(int lst, int sum) {
	if (f.size() > r.size()) return;
	if (check()) {
		int s = n + 1, c = fac[f.size()], s1 = 0;
		for (int i = 0, j; i < f.size(); i = j) {
			for (j = i + 1; j < f.size() && f[j] == f[i]; ++j);
			c = 1ll * c * ifac[j - i] % P;
			if (f[i] > 1) s += 2 * (j - i);
			s1 += 2 * f[i] * (j - i);
		}
		ans = (ans + 1ll * c * fac[s] % P * ifac[s1] % P * ifac[s - s1]) % P;
	}
	for (int i = lst; (sum + max(1, i - 1)) * 2 <= n + 1; ++i) f.push_back(i), dfs(i, sum + max(1, i - 1)), f.pop_back();
}

int main() {
	scanf("%d%d%s", &n, &k, s + 1);
	for (int i = 1; i <= k; ++i)
		if (s[i] == 'r') r.push_back(i);
	for (int i = fac[0] = 1; i <= 2 * n + 5; ++i) fac[i] = 1ll * fac[i - 1] * i % P;
	ifac[2 * n + 5] = power(fac[2 * n + 5], P - 2);
	for (int i = 2 * n + 5; i; --i) ifac[i - 1] = 1ll * ifac[i] * i % P;
	dfs(1, 0);
	printf("%d\n", ans);
	return 0;
}