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>

#define reg register
#define pr std::pair<int, int>
#define fi first
#define se second
#define FIN(s) freopen(s, "r", stdin)
#define FOUT(s) freopen(s, "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define lep(i, l, r) for (int i = l; i < r; ++i)
#define irep(i, r, l) for (int i = r; i >= l; --i)
#define ilep(i, r, l) for (int i = r; i > l; --i)
#define Rep(i, n) rep(i, 1, n)
#define Lep(i, n) lep(i, 1, n)
#define IRep(i, n) irep(i, n, 1)
#define ILep(i, n) ilep(i, n, 1)
typedef long long ll;
typedef long double ld;

namespace modular {
    const int MOD = 1000000007;
    inline int add(int x, int y) { return (x += y) >= MOD ? x -= MOD : x; }
    inline void inc(int &x, int y) { (x += y) >= MOD ? x -= MOD : 0; }
    inline int mul(int x, int y) { return 1LL * x * y % MOD; }
    inline int qpow(int x, int y) {
        int ans = 1;
        for (; y; y >>= 1, x = mul(x, x))
            if (y & 1) ans = mul(ans, x);
        return ans;
    }
};  // namespace modular
using namespace modular;

namespace Base {
    template <typename Tp>
    inline Tp input() {
        Tp x = 0, y = 1;
        char c = getchar();
        while ((c < '0' || '9' < c) && c != EOF) {
            if (c == '-') y = -1;
            c = getchar();
        }
        if (c == EOF) return 0;
        while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
        return x *= y;
    }
    template <typename Tp>
    inline void read(Tp &x) {
        x = input<Tp>();
    }
    template <typename Tp>
    inline void chmax(Tp &x, Tp y) {
        x < y ? x = y : 0;
    }
    template <typename Tp>
    inline void chmin(Tp &x, Tp y) {
        x > y ? x = y : 0;
    }
};  // namespace Base
using namespace Base;
/*----------------------------------------------------------------------------*/

#define MAX_N 107

int N, K, tot, res;
int mch[MAX_N], pos[MAX_N], sum[MAX_N];
int fac[MAX_N * 3], ifac[MAX_N * 3];
char s[MAX_N];
bool vis[MAX_N];

inline int C(int x, int y) {
    if (y < 0 || x < y) return 0;
    return mul(fac[x], mul(ifac[y], ifac[x - y]));
}

void init() {
    int MX = 300;
    fac[0] = ifac[0] = 1;
    Rep(i, MX) fac[i] = mul(fac[i - 1], i);
    ifac[MX] = qpow(fac[MX], MOD - 2);
    irep(i, MX, 2) ifac[i - 1] = mul(ifac[i], i);
    Rep(i, K) if (s[i] == 'r') {
        pos[++tot] = i;
        rep(j, i + 1, K) if (s[j] == 'b' && !vis[j]) {
            mch[i] = j;
            vis[j] = true;
            break;
        }
    }
}

int tp[MAX_N];
bool check(int cur) {
    if (cur > tot) return false;
    Rep(i, K) sum[i] = 0;
    int p = 1;
    IRep(i, cur) {
        sum[pos[i]]++;
        if (tp[p] > 1) {
            if (!mch[pos[i]]) return false;
            sum[mch[pos[i]]] += tp[p] - 1;
        }
        p++;
    }
    IRep(i, K) {
        sum[i] += sum[i + 1];
        if (sum[i] > K - i + 1) return false;
    }
    return true;
}

bool dfs(int deg, int pre, int len) {
    if (!check(deg - 1)) return false;
    int t = deg;
    Lep(i, deg) t += 2 * tp[i] - 1;
    int ans = mul(C(N - len + t - 1, t - 1), fac[deg - 1]), tmp = 1;
    Lep(i, deg) {
        if (tp[i] != tp[i - 1]) {
            ans = mul(ans, ifac[tmp]);
            tmp = 0;
        }
        ++tmp;
    }
    ans = mul(ans, ifac[tmp]);
    // printf("%d:  ", ans);
    // Lep(i, deg) printf("%d ", tp[i]);
    // puts("");
    inc(res, ans);
    if (deg > tot) return true;
    rep(i, pre, 70) {
        int L = len;
        if (deg > 1) L++;
        if (i == 1)
            L++;
        else
            L += i - 2 + i - 1;
        if (L > N) break;
        tp[deg] = i;
        if (!dfs(deg + 1, i, L)) break;
    }
    return true;
}

void solve() {
    dfs(1, 1, 0);
    printf("%d\n", res);
}

int main() {
    read(N), read(K);
    scanf("%s", s + 1);
    init();
    solve();
    return 0;
}