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:
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int maxN = 200;
char c[maxN];
int n, k;
int sz = 0;
int red[maxN];
int blue[maxN];
int r = 1;
int cnt1[3 * maxN];
int cnt2[3 * maxN];
int ans = 0;
int LIM;
int F = 0;
int mark[maxN];
const int mod = (int)1e9 + 7;
int mult(int a, int b) {
    return (1LL * a * b) % mod;
}
int sum(int a, int b) {
    int s = a + b;
    if (s >= mod) s -= mod;
    return s;
}
int fact[2 * maxN];
int invfact[2 * maxN];
int inv[2 * maxN];
int cnk(int n, int k) {
    if (n < k || k < 0) return 0;
    return mult(fact[n], mult(invfact[n - k], invfact[k]));
}
int lstB[2 * maxN];
bool check() {
    memset(mark, -1, sizeof mark);
    int ptr = 0;
    while (ptr < sz && blue[ptr] == 0) {
        ptr++;
    }
    ptr--;
    //[0 .. ptr] - ok
    //
    int ptrR = sz - 1;
    int ptrB = sz - 1;
    for (int i = 1; i <= k; i++) {
        if (c[i] == 'r' && ptrR >= 0) {
            ptrR--;
            mark[i] = 1;
        }
        if (c[i] == 'b' && ptrB > ptrR && ptrB > ptr) {
            lstB[ptrB] = i;
            ptrB--;
            mark[i] = 1;
        }
    }
    //rrrrrrrbr
    if (ptrR != -1 || ptrB != ptr) return false;
    int where = sz - 1;
    int need = red[sz - 1];
    for (int i = 1; i <= k; i++) {
        if (need == 0) return true;
        if (mark[i] == 1) continue;
        if (where > ptr && lstB[where] <= i) {
            need--;
            if (need == 0) {
                where--;
                need = red[where];
            }
        }
    }
    return (need == 0 || where == ptr);
}
int his_cnt[maxN];
void calc() {
    if (!check()) {
        return;
    }

    int val = fact[sz];
    memset(his_cnt, 0, sizeof his_cnt);
    int groups = 0;
    int other = 0;
    for (int i = 0; i < sz; i++) {
        his_cnt[blue[i]]++;
        val = mult(val, inv[his_cnt[blue[i]]]);
        groups += blue[i] + red[i];
        if (blue[i]) other++;
    }
    //so we have
    // x_1 + ... + x_groups + y_1 + .. + y_2*other + c_1 + c_2 + p_1 + ... + p_(sz - 1) = n
    // groups + 2 * other + sz - 1 + 2
    int all_gr = groups + 2 * other + sz - 1 + 2;
    ans = sum(ans, mult(val, cnk(n + all_gr - 1 - groups - (sz - 1), all_gr - 1)));
}
void gen(int pos, int total) {
    if (total + sz - 1 > n) return;
    if (sz > LIM) return;
    if (pos == r) {
        F++;
        calc();
        return;
    }
    gen(pos + 1, total);
    if (pos == 0) {
        red[sz] = 1;
        blue[sz] = 0;
        sz++;
        gen(pos, total + 1);
        sz--;
    }
    else {
        red[sz] = cnt1[pos];
        blue[sz] = cnt2[pos];
        sz++;
        gen(pos, total + red[sz - 1] + blue[sz - 1]);
        sz--;
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    fact[0] = invfact[0] = fact[1] = invfact[1] = inv[1] = 1;
    for (int i = 2; i < 2 * maxN; i++) {
        fact[i] = mult(fact[i - 1], i);
        inv[i] = mult(inv[mod % i], mod - mod / i);
        invfact[i] = mult(invfact[i - 1], inv[i]);
    }

    cin >> n >> k;
    for (int i = 1; i <= k; i++) cin >> c[i];
    LIM = (n + 1) / 2;
    for (int d = 1; d <= n; d++) {
        cnt1[r] = d - 1;
        cnt2[r] = d;
        r++;
    }
    gen(0, 0);
    cout << ans;
    return 0;
}