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 N = 75, K = 75;
const long long mod = 1000000007ll;

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

long long solve () {
	queue<int> que;
	for (int i = 0; i < m; i++) suf[i] = 1;
	for (int i = 0, j = top - 1; i < m && j >= 0; i++) {
		if (str[i] == 'r') que.push(i);
		if (stk[j] && str[i] == 'b' && !que.empty()) {
			suf[que.front()] = suf[i] = 0;
			que.pop();
			pos[j--] = i;
		}
		while (j >= 0 && !stk[j] && !que.empty()) {
			suf[que.front()] = 0, que.pop();
			pos[j--] = i;
		}
		if (i == m - 1 && j >= 0) return 0ll;
	}

	suf[m] = 0;
	for (int i = m - 1; i >= 0; i--) suf[i] += suf[i + 1];
	for (int i = 0, j = 0; i < top; i++) {
		if (stk[i]) {
			j += stk[i] - 1;
			if (suf[pos[i]] < j) 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];
		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++;
	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;
}