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;
constexpr int P = 1E9 + 7, N = 200;
int power(int base, int exp) {
    int result = 1;
    while (exp > 0) {
        if (exp & 1)
            result = 1LL * result * base % P;
        base = 1LL * base * base % P;
        exp >>= 1;
    }
    return result;
}
int main() {
    array<int, 200> factorial, inv_factorial;
    factorial[0] = 1;
    for (int i = 1; i < N; ++i)
        factorial[i] = 1LL * factorial[i - 1] * i % P;
    inv_factorial[N - 1] = power(factorial[N - 1], P - 2);
    for (int i = N - 1; i >= 1; --i)
        inv_factorial[i - 1] = 1LL * inv_factorial[i] * i % P;
    auto binom = [&](int n, int m) {return 1LL * factorial[n] * inv_factorial[m] % P * inv_factorial[n - m] % P;};
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    string s;
    cin >> n >> k >> s;
    vector<int> f;
    int ans = 0;
    auto work = [&]() {
        int len = n - (int)f.size() + 1;
        int bl = (int)f.size() + 1;
        vector<bool> book(k);
        vector<int> r(f.size());
        for (int i = 0, j = 0; i < (int)f.size(); ++i) {
            len -= max(1, 2 * f[i] - 3);
            bl += max(1, 2 * f[i] - 3);
            while (j < k && s[j] != 'r')
                ++j;
            if (j == k)
                return;
            book[j] = true;
            r[i] = j++;
        }
        for (int i = 0, j = 0; i < (int)f.size(); ++i) {
            if (f[i] == 1)
                continue;
            bl += 2;
            j = max(j, r[i]);
            while (j < k && (s[j] != 'b' || book[j]))
                ++j;
            if (j == k)
                return;
            book[j] = true;
            r[i] = j++;
        }
        for (int i = 0, j = 0; i < (int)f.size(); ++i) {
            for (int l = 0; l < f[i] - 2; ++l) {
                j = max(j, r[i]);
                while (j < k && book[j])
                    ++j;
                if (j == k)
                    return;
                r[i] = j++;
            }
        }
        int result = factorial[f.size()];
        for (int i = 0; i < (int)f.size(); ) {
            int j = i;
            while (j < (int)f.size() && f[i] == f[j])
                ++j;
            result = 1LL * result * inv_factorial[j - i] % P;
            i = j;
        }
        result = 1LL * result * binom(len + bl - 1, bl - 1) % P;
        ans = (ans + result) % P;
    };
    function<void(int, int)> dfs = [&](int sum, int last) {
        work();
        for (int i = 1; i <= last && max(2, 2 * i - 2) <= sum; ++i) {
            f.push_back(i);
            dfs(sum - max(2, 2 * i - 2), i);
            f.pop_back();
        }
    };
    dfs(n + 1, n + 1);
    cout << ans << endl;
    return 0;
}