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 EB emplace_back

typedef std::vector <int> vector;
typedef long long ll;
const int N = 162, mod = 1000000007;

int n, len, ans = 0;
int fact[N], inv[N], finv[N], C[N][N];
int a[N], b[N];
vector rem[N][N];

inline void add(int &x, const int y) {x += y - mod, x += x >> 31 & mod;}
ll PowerMod(ll a, int n, ll c = 1) {for (; n; n >>= 1, a = a * a % mod) if (n & 1) c = c * a % mod; return c;}

void init() {
	int i, j;
	for (inv[1] = 1, i = 2; i < N; ++i) inv[i] = ll(mod - mod / i) * inv[mod % i] % mod;
	for (*C[0] = i = 1; i < N; ++i)
		for (*C[i] = j = 1; j <= i; ++j) add(C[i][j] = C[i - 1][j], C[i - 1][j - 1]);
}

void dfs(int dep, int last, int cur, int n_r, int prod) {
	int i, s = 0, nxt = cur + 2, n_rb = dep - n_r;
	vector &U = rem[n_r][n_rb];
	if (U.empty()) return;
	for (i = n_rb - 1; i >= 0; --i)
		if ((s += a[i] - 1) > U[n_rb - i]) return;
	ans = (ans + (ll)prod * C[n + 1 + n_rb * 2][(s + n_rb * 2 + n_r) * 2]) % mod;
	prod = prod * (dep + 1ll) % mod;
	if (nxt <= n + 1)
		a[dep] = 0, b[dep] = (last ? 0 : b[dep - 1]) + 1,
		dfs(dep + 1, 0, nxt, n_r + 1, (ll)prod * inv[b[dep]] % mod);
	for (i = 1; i <= last && nxt <= n + 1; ++i, nxt += 2)
		a[dep] = i, b[dep] = (i == last ? b[dep - 1] : 0) + 1,
		dfs(dep + 1, i, nxt, n_r, (ll)prod * inv[b[dep]] % mod);
}

int main() {
	int i, j, k, n_B, c_R, c_RB, poi[N];
	int h, t, que[N];
	bool used[N]; char s[N];
	scanf("%d%d%s", &n, &len, s), init();
	n_B = std::count(s, s + len, 98);
	for (i = 0; i <= len; ++i)
		for (j = 0; j <= n_B; ++j) {
			c_R = c_RB = h = t = 0, memset(used, false, len);
			for (k = 0; k < len && c_RB < j; ++k)
				if (s[k] == 114) que[t++] = k;
				else if (h != t) used[ poi[c_RB++] = k ] = used[ que[h++] ] = true;
			for (k = 0; k < len && c_R < i; ++k)
				if (!used[k] && s[k] == 114) ++c_R, used[k] = true;
			if (c_RB < j || c_R < i) continue;
			vector &res = rem[i][j];
			res.reserve(j + 1), res.EB(0);
			for (t = 0, k = len - 1; k >= 0 && c_RB; --k)
				if (t += !used[k], k == poi[c_RB - 1]) res.EB(t), --c_RB;
			assert((int)res.size() == j + 1);
		}
	dfs(0, INT_MAX, 0, 0, 1);
	printf("%d\n", ans);
	return 0;
}