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 <cstdio>
#include <algorithm>
#include <cstring>
#include <cassert>
using namespace std;

typedef long long i64;
const int MAX_N = 205, MOD = 1000000007;

i64 fac[MAX_N], inv[MAX_N], ifac[MAX_N];
i64 result = 0;

int N, K;
char S[MAX_N];

i64 binom(int n, int m) {
  if (n < m) return 0;
  return fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}

int tot = 0, pos[MAX_N], st[MAX_N];

bool check() {
  static bool vis[105];
  static int posb[105];
  memset(vis, 0, sizeof vis);
  for (int i = 1; i <= tot; ++i)
    if (pos[i])
      vis[pos[i]] = 1;
    else
      return false;
  for (int i = 1, j = 1; i <= tot; ++i) {
    j = max(j, pos[i]);
    if (st[i] == 1) break;
    while (j <= K && S[j] != 'b') j++;
    if (j > K) return false;
    vis[j] = 1, j++;
    posb[i] = j;
  }
  for (int i = 1, j = 1; i <= tot; ++i) {
    int cnt = st[i] - 2;
    j = max(j, posb[i]);
    while (cnt > 0 && j <= K) {
      if (!vis[j]) cnt--;
      vis[j] = 1, j++;
    }
    if (cnt > 0) return false;
  }
  return true;
}

void dfs(int rest, int restN, int lim) {
  if (restN < 0 || rest < 0) return;
  if (rest >= 0) {
    if (!check()) return;
    i64 now = fac[tot];
    int cnt = 0, sum_len = 0;
    for (int i = 1; i <= tot; ++i) {
      if (st[i] == 1) {
	now = now * ifac[tot - i + 1] % MOD;
	sum_len += tot - i + 1;
	break;
      } else {
	int j = i, num = 0;
	while (st[j + 1] == st[i]) j++;
	num = j - i + 1, cnt += num, sum_len += num * (st[i] * 2 - 3);
	now = now * ifac[num] % MOD;
	i = j;
      }
    }
    assert(sum_len == N - restN);
    i64 temp = 0;
    for (int i = 0; i <= N - sum_len; ++i) {
      int l = sum_len + i;
      temp = (temp + now * binom(cnt * 2, i) % MOD * binom(N + 1, l + tot) % MOD) % MOD;
    }
    result = (result + temp) % MOD;
  }
  for (int i = lim; i; --i) {
    st[++tot] = i;
    dfs(rest - i, restN - max(i * 2 - 3, 1), i);
    tot--;
  }
}

int main() {
  fac[0] = ifac[0] = inv[1] = 1;
  for (int i = 1; i < MAX_N; ++i) fac[i] = fac[i - 1] * i % MOD;
  for (int i = 2; i < MAX_N; ++i) inv[i] = -(MOD / i) * inv[MOD % i] % MOD;
  for (int i = 1; i < MAX_N; ++i) ifac[i] = ifac[i - 1] * inv[i] % MOD;
  
  scanf("%d%d", &N, &K);
  scanf("%s", S + 1);
  
  for (int i = 1, temp = 0; i <= K; ++i)
    if (S[i] == 'r') pos[++temp] = i;

  dfs(K, N, K);

  printf("%lld\n", (result + MOD) % MOD);
  return 0;
}