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 <cstring>
#include <algorithm>
#include <vector>
#include <queue>

const int MOD = (int)1e9 + 7;
const int kN = 70 + 1;
const int kM = 10000;
int n, k;
char s[kN];
int Inv[kM], F[kM], Finv[kM];

int binom(int a, int b)
{
    if (b < 0 || b > a) return 0;
    return F[a] * 1LL * Finv[b] % MOD * Finv[a - b] % MOD;
}

inline void add(int &a, int b)
{
    a += b;
    if (a >= MOD) a -= MOD;
}

std::vector<int> vec; // 每段B的数量

int getBound(const std::vector<int> &vec)
{
    std::vector<int> used(k);
    int j = 0, pa = 0;
    for (int i = 0; i < k; ++ i) {
        if (s[i] == 'r') {
            if (pa < vec.size())
                used[i] = -1, ++ pa;
        } else if (j < pa) {
            used[i] = 1;
            ++ j;
        }
    }
    if (j != vec.size()) return -1;
    int left[2] = {};
    j = 0;
    for (int i = k - 1; i >= 0; -- i) {
        if (used[i] == 0) {
            left[s[i] == 'b'] ++;
        } else if (used[i] > 0) {
            int c = vec[j ++] - 1;
            for (int w = 1; w >= 0; -- w) {
                int tmp = std::min(left[w], c);
                c -= tmp;
                left[w] -= tmp;
            }
            if (c > 0) return -1;
        }
    }
    return left[0];
}

int calc(const std::vector<int> &vec)
{
    int bound_a = getBound(vec);
    if (bound_a < 0) return 0;
    int ret = 0;
    for (int a = 0; a <= bound_a; ++ a) {
        int segc = vec.size() + a;
        if (segc == 0) {
            add(ret, 1); continue;
        }
        int pre = ret;
        int len = a;
        int hole = 1 + a * 2;
        int ops = a;
        for (int x : vec) len += x * 2 - 1, hole += x * 2 + 1 + 1, ops += x + 1;
        if (ops > k || segc - 1 + len > n) break;
        int coef = F[segc] * 1LL * Finv[a] % MOD;
        for (int i = 0, j = 0; i < vec.size(); i = j ++) {
            while (j < vec.size() && vec[j] == vec[i]) ++ j;
            coef = coef * 1LL * Finv[j - i] % MOD;
        }
        add(ret, binom(n - len - segc + 1 + hole - 1, hole - 1) * 1LL * coef % MOD);
    }
    return ret;
}

int search(int at, int segc, int len, int ops)
{
    int ret = calc(vec);
    if (ret == 0) return 0;
    for (int i = at; ; ++ i) {
        if (k < ops + i + 1 || n < segc + len + i * 2 - 1) break;
        int h = vec.size();
        for (int j = 1; ; ++ j) {
            if (k < ops + (i + 1) * j || n < segc + j - 1 + len + (i * 2 - 1) * j) break;
            vec.emplace_back(i);
            add(ret, search(i + 1, segc + j, len + (i * 2 - 1) * j, ops + (i + 1) * j));
        }
        vec.resize(h);
    }
    return ret;
}

int main()
{
    Inv[1] = 1;
    for (int i = 2; i < kM; ++ i)
        Inv[i] = (MOD - MOD / i) * 1LL * Inv[MOD % i] % MOD;
    F[0] = Finv[0] = 1;
    for (int i = 1; i < kM; ++ i) {
        F[i] = F[i - 1] * 1LL * i % MOD;
        Finv[i] = Finv[i - 1] * 1LL * Inv[i] % MOD;
    }
    scanf("%d%d%s", &n, &k, s);
    printf("%d\n", search(1, 0, 0, 0));
}