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;

typedef long long ll;
const int N = 301, mod = 1000000007;
int n, k, ans = 0;
char s[N];
int fac[N], inv[N];

int f[N], m = 0, r[N], b[N], visit[N];
inline void solve() {
  for (int i = 1; i <= k; i++) visit[i] = 0;
  for (int i = 1, j = 1; i <= m; i++, j++) {
    while (j <= k && s[j] != 'r') j++;
    if (j > k) return;
    r[i] = j;
    visit[j] = 1;
  }
  for (int i = 1, j = 1; i <= m; i++, j++) if (f[i] >= 2) {
    j = max(j, r[i]);
    while (j <= k && s[j] != 'b') j++;
    if (j > k) return;
    b[i] = j;
    visit[j] = 1;
  }
  for (int i = 1, j = 1; i <= m; i++) if (f[i] >= 3) {
    int x = f[i] - 2;
    j = max(j, b[i]);
    while (x--) {
      while (j <= k && visit[j]) j++;
      if (j > k) return;
      visit[j] = 1;
      j++;
    }
  }
  int coef = fac[m];
  for (int i = 1, j = 0; i <= m; i++) {
    j = f[i] != f[i - 1] ? 1 : j + 1;
    coef = (ll) coef * fac[j - 1] % mod * inv[j] % mod;
  }
  int upper = n + 1, lower = 0;
  for (int i = 1; i <= m; i++) {
    if (f[i] >= 2) upper += 2;
    lower += f[i] * 2;
  }
  if (upper < lower) return;
  coef = (ll) coef * fac[upper] % mod * inv[lower] % mod * inv[upper - lower] % mod;
  ans = (ans + coef) % mod;
}
void dfs(int x, int last) {
  solve();
  for (int i = last; i; i--) {
    int y = (i == 1 ? 1 : 2 * i - 3) + 1;
    if (x >= y) {
      f[++m] = i;
      dfs(x - y, i);
      --m;
    }
  }
}

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