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;
const int mod = 1000000007;
int n, m, posr[N], cr, a[N], fact[301], ifact[301], inv[301];
char S[N];
int ans;
inline void Init() {
	inv[1] = 1;
	for (int i = 2; i <= 300; i++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
	fact[0] = ifact[0] = 1;
	for (int i = 1; i <= 300; i++) {
		fact[i] = 1ll * fact[i - 1] * i % mod;
		ifact[i] = 1ll * ifact[i - 1] * inv[i] % mod;
	}
}
inline void calc(int cnt, int sum) {
	if (!cnt) { ans = (ans + 1) % mod; return; }
	if (cr < cnt) return;
	int R[N], B[N], vis[N];
	for (int i = 1; i <= m; i++) vis[i] = 0;
	int fir1 = cnt + 1;
	for (int i = 1, posb = 1; i <= cnt; i++) {
		if (a[i] == 1) {
			fir1 = i;
			while (i <= cnt) {
				R[i] = B[i] = posr[i];
				vis[R[i]] = 1;
				i++;
			}
			break;
		}
		if (posb < posr[i]) posb = posr[i] + 1;
		while (posb <= m && S[posb] != 'b') posb++;
		if (posb > m) return;
		R[i] = posr[i];
		B[i] = posb;
		vis[R[i]] = vis[B[i]] = 1;
		posb++;
	}
	for (int i = fir1 - 1, j = m, ss = 0, ps = 0; i; i--) {
		while (j > B[i]) {
			if (!vis[j]) ss++;
			j--;
		}
		if (ss - ps < a[i] - 2) return;
		ps += a[i] - 2;
	}
	int res = fact[cnt], cp = 1;
	for (int i = 1, j = 0; i <= cnt; i++) {
		j++;
		cp += a[i] * 2;
		if (i == cnt || a[i] != a[i + 1]) {
			res = 1ll * res * ifact[j] % mod;
			j = 0;
		}
	}
	res = 1ll * res * fact[n - sum + cp] % mod * ifact[cp - 1] % mod * ifact[n - sum + 1] % mod;
	ans = (ans + res) % mod;
}
void go(int d, int mx, int sum) {
	calc(d - 1, sum);
	if (sum + 1 <= n) {
		a[d] = 1;
		go(d + 1, 1, sum + 2);
	}
	for (int i = 2; i <= mx; i++) {
		if (sum + 2 * i - 3 <= n) {
			a[d] = i;
			go(d + 1, i, sum + 2 * i - 2);
		}
	}
}
int main() {
	Init();
	scanf("%d%d %s", &n, &m, S + 1);
	cr = 0;
	for (int i = 1; i <= m; i++) {
		if (S[i] == 'r') posr[++cr] = i;
	}
	go(1, (n + 3) >> 1, 0);
	printf("%d\n", ans);
	return 0;
}