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 maxn = 1000, mod = 1e9 + 7;
int N, k, tot, ans, fac[maxn + 10], ifac[maxn + 10], inv[maxn + 10];
int a[100], pos[100], cnt[100];
char s[100];
bool vis[100];

void solve(int n) {
	memset(vis, 0, sizeof vis);
	for (int i = 1, p = 1; i <= n; ++i) {
		for (; p <= k && s[p] != 'r'; ++p);
		if (p > k) return;
		vis[p] = 1;
		pos[i] = p++;
	}
	for (int i = 1, p = 1; i <= n; ++i)
		if (a[i] >= 2) {
			for (; p <= k && (p <= pos[i] || s[p] != 'b'); ++p);
			if (p > k) return;
			vis[p] = 1; pos[i] = p++;
		}
	for (int i = 1, p = 1; i <= n; ++i)
		if (a[i] >= 3)
			for (int j = 1; j <= a[i] - 2; ++j) {
				for (; p <= k && (p <= pos[i] || vis[p]); ++p);
				if (p > k) return;
				++p;
			}
	int ans = fac[n];
	memset(cnt, 0, sizeof cnt);
	for (int i = 1; i <= n; ++i)
		++cnt[a[i]];
	for (int i = 1; i <= N; ++i)
		if (cnt[i])
			ans = 1ll * ans * ifac[cnt[i]] % mod;
	int x = N + 1, y = 0;
	for (int i = 1; i <= n; ++i) {
		if (a[i] >= 2) x += 2;
		y += a[i] * 2;
	}
	if (x < y) return;
	ans = 1ll * ans * fac[x] % mod;
	ans = 1ll * ans * ifac[y] % mod;
	ans = 1ll * ans * ifac[x - y] % mod;
	(tot += ans) %= mod;
}

void dfs(int p, int l, int mx) {
	solve(p - 1);
	for (int i = mx; i >= 1; --i)
		if (max(i * 2 - 3, 1) <= l) {
			a[p] = i;
			dfs(p + 1, l - max(i * 2 - 3, 1), i);
		}
}

int main() {
	fac[0] = ifac[0] = 1;
	for (int i = 1; i <= maxn; ++i) {
		fac[i] = 1ll * fac[i - 1] * i % mod;
		inv[i] = i == 1 ? 1 : mod - 1ll * (mod / i) * inv[mod % i] % mod;
		ifac[i] = 1ll * ifac[i - 1] * inv[i] % mod;
	}
	scanf("%d%d", &N, &k);
	scanf("%s", s + 1);
	dfs(1, N, N * 2);
	printf("%d", tot);
}