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 <cassert>

#define P 1000000007
#define int long long

using namespace std;

typedef long long ll;

char ch[77];

void add(int &x, int y) {
    x = (x + y) % P;
}

int n, K, Fac[333], Rev[333], X[77], C[333][333], ans = 0;

ll powmod(ll x, ll y = P - 2, ll p = P) {
    ll ans = 1;
    while(y) {
        if(y & 1) ans = ans * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return ans;
}
int ts = 0;
void calc(int sz) {
    ts++;
    int tb = 0, tr = 0;
    int used[77], TR[77], TB[77];
    memset(used, 0, sizeof used);
    for(int i = 1; i <= sz; i++) {
        tr++;
        while(tr <= K && ch[tr] != 'r') tr++;
        used[tr] = 1;
        if(X[i] > 1) {
            tb = max(tb + 1, tr);
            while(tb <= K && (ch[tb] != 'b' || used[tb])) tb++;
            used[tb] = 1;
            TR[i] = tr;
            TB[i] = tb;
        } else {
            TR[i] = tr;
            TB[i] = tr;
        }
        if(tr > K || tb > K) return;
    }
    for(int i = 1; i <= sz; i++) {
        int tt = TB[i];
        for(int j = 1; j <= X[i] - 2; j++) {
            while(tt <= K && used[tt]) tt++;
            used[tt] = 1;
            if(tt > K) return;
        }
    }
    int t = 0, rw = 0, bw = 0;
    for(int i = 1; i <= sz; i++)
        if(X[i] == 1) {
            rw++;
            t++;
        } else {
            bw += X[i] - 1;
            rw += X[i];
            t += X[i] * 2 - 3;
        }
    t = n + 1 - t - sz;
    if(t < 0) return;
    ll tmp = Fac[sz];
    X[sz + 1] = 0; //!!!
    for(int i = 2, lst = 1; i <= sz + 1; i++)
        if(X[i] != X[lst]) {
            tmp = tmp * Rev[i - lst] % P;
            lst = i;
        }
    for(int r = 0; r <= t; r++)
        for(int b = 0; r + b <= t; b++) {
            add(ans, (!rw ? !r : C[r + rw - 1][r]) * (!bw ? !b : C[b + bw - 1][b]) % P * C[sz + (t - r - b)][sz] % P * tmp);
        }
}

void Search(int x, int lst, int tbr, int tot = 0) {
    calc(x - 1);
    for(int i = 1; i <= lst && i + tbr <= K && max(2ll, i * 2 - 2) + tot <= n + 3; i++) {
        X[x] = i;
        Search(x + 1, i, tbr + i, tot + max(2ll, i * 2 - 2));
    }
}

#undef int
int main() {
#define int long long
    for(int i = 0; i < 333; i++)
        for(int j = 0; j <= i; j++)
            C[i][j] = !j ? 1 : (C[i - 1][j - 1] + C[i - 1][j]) % P;
    for(int i = 0; i < 333; i++) Fac[i] = !i ? 1 : Fac[i - 1] * i % P;
    for(int i = 332; i >= 0; i--) Rev[i] = i == 332 ? powmod(Fac[i]) : Rev[i + 1] * (i + 1) % P;
    scanf("%lld%lld", &n, &K);
    scanf("%s", ch + 1);
    Search(1, K, 0);
    //printf("%d\n", ts);
    printf("%lld\n", (ans % P + P) % P);
    return 0;
}