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>
#define debug(x) cerr << #x << " " << (x) << endl
using namespace std;

const int N = 75, K = 75;
const long long mod = 1000000007ll;

int n, m, stk[N], pos[N], suf[K], tmp[N], top = 0;
char str[K];
bool vis[K];
long long c[N * 5][N * 5], ans = 0ll;

bool check () {
	vector<int> vec1, vec2, vec3;
	for (int i = 0; i < top; i++) vec1.push_back(stk[i]);
	for (int i = 0; i < m; i++) {
		if (str[i] == 'r') {
			if (!vec1.empty()) {
				if (vec1.back()) vec2.insert(vec2.begin(), vec1.back());
				vec1.pop_back();
			}
			else if (!vec3.empty()) {
				(*vec3.rbegin())--;
				if (!vec3.back()) vec3.pop_back();
			}
		}
		else {
			if (!vec2.empty()) {
				if (vec2.back() > 1) vec3.push_back(vec2.back() - 1);
				vec2.pop_back();
			}
			else if (!vec3.empty()) {
				(*vec3.rbegin())--;
				if (!vec3.back()) vec3.pop_back();
			}
		}
	}
	return vec1.empty() && vec2.empty() && vec3.empty();
}
long long solve () {
	if (!check()) return 0ll;
	long long res = 1ll;
	for (int i = 0; i <= n; i++) tmp[i] = 0;
	for (int i = 0; i < top; i++) tmp[stk[i]]++;
	for (int i = 0, j = 0; i <= n; i++) {
		j += tmp[i];
		assert(j <= n * 3 && tmp[i] <= n * 3);
		res = res * c[j][tmp[i]] % mod;
	}

	int num1 = 0, num2 = 0;
	for (int i = 0; i < top; i++) {
		if (stk[i]) num1 += 2 * stk[i] - 1, num2 += 2;
		else num1++;
	}
	if (top) num1 += top - 1, num2 += 2;
	else num1++;
	if (n + num2 - 1 < 0 || num1 + num2 - 1 < 0) return 0ll;
	if (n + num2 - 1 > n * 5 || num1 + num2 - 1 > n * 5) return 0ll;
	res = res * c[n + num2 - 1][num1 + num2 - 1] % mod;
	return res;
}

void dfs (int mn, int total) {
	if (mn == n + 1) ans = (ans + solve()) % mod;
	if (mn <= n) dfs(mn + 1, total);
	int t = mn ? mn << 1 : 2;
	if (total + t <= n + 1) {
		stk[top++] = mn;
		dfs(mn, total + t);
		top--;
	}
}

int main () {
	scanf("%d%d%s", &n, &m, str);
	for (int i = 0; i <= n * 5; i++) {
		for (int j = 0; j <= n * 5; j++) c[i][j] = 0ll;
	}
	for (int i = 0; i <= n * 5; i++) c[i][0] = c[i][i] = 1ll;
	for (int i = 1; i <= n * 5; i++) {
		for (int j = 1; j < i; j++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
	}
	dfs(0, 0);
	printf("%lld\n", ans);
	return 0;
}