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>

const int MAXN = 80;
const int mod = 1000000007;
typedef long long LL;
void reduce(int & x) { x += x >> 31 & mod; }
int mul(int a, int b) { return (LL) a * b % mod; }
int fastpow(int a, int b, int res = 1) {
	for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a);
	return res;
}
int li[MAXN];
char buf[MAXN];
int n, K, ans;
const int MAXS = 300;
int tl[MAXN], C[MAXS][MAXS];
int fac[MAXN], inv[MAXN];
void dfs(int S, int rest, int can, int lst) {
	if (rest < 0) return ;
	memcpy(tl + 1, li + 1, S << 2);
	int cur1 = 1, cur2 = 1, cur3 = 1;
	for (int i = 1; i <= K; ++i) {
		bool ok = false;
		if (cur1 <= S && buf[i] == 'r') {
			++cur1; ok = true;
		}
		while (cur2 < cur1 && tl[cur2] == 0) ++cur2;
		if (!ok && cur2 + 1 <= cur1 && buf[i] == 'b') {
			--tl[cur2++]; ok = true;
		}
		while (cur2 < cur1 && tl[cur2] == 0) ++cur2;
		if (!ok && cur3 < cur2 && tl[cur3]) --tl[cur3];
		while (cur3 < cur2 && tl[cur3] == 0) ++cur3;
	}
	if (cur3 <= S) return ;
	int tx = mul(C[can + rest - 1][can - 1], fac[S]);
	static int hav[MAXN];
	memset(hav, 0, n + 1 << 2);
	for (int i = 1; i <= S; ++i) ++hav[li[i]];
	for (int i = 0; i <= n; ++i) if (hav[i]) tx = mul(tx, inv[hav[i]]);
	reduce(ans += tx - mod);
	for (int i = lst; ~i; --i) {
		li[S + 1] = i;
		dfs(S + 1, rest - std::max(i, 1) * 2 + (S == 0), can + (i + 1) * 2, i);
	}
}
int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	for (int i = 0; i != MAXS; ++i) {
		C[i][0] = 1;
		for (int j = 1; j <= i; ++j)
			reduce(C[i][j] = C[i - 1][j] + C[i - 1][j - 1] - mod);
	}
	std::cin >> n >> K >> buf + 1;
	inv[0] = inv[1] = fac[0] = fac[1] = 1;
	for (int i = 2; i <= n; ++i) {
		inv[i] = mul(inv[mod % i], mod - mod / i);
		fac[i] = mul(fac[i - 1], i);
	}
	for (int i = 2; i <= n; ++i) inv[i] = mul(inv[i - 1], inv[i]);
	dfs(0, n, 1, n);
	std::cout << ans << std::endl;
	return 0;
}