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;

typedef long long ll;

const int MAX_N = 200;
const ll MOD = 1e9 + 7;

ll sq(ll x) { return x * x % MOD; }
ll qpow(ll a, ll b) { return b ? sq(qpow(a, b / 2)) * (b & 1 ? a : 1) % MOD : 1; }
ll inv(ll x) { return qpow(x, MOD - 2); }

int N, K, cnt[MAX_N];
char S[MAX_N];
ll fac[MAX_N], ifac[MAX_N];
ll ans;

ll comb(int n, int m) { return m <= n && m >= 0 ? fac[n] * ifac[n - m] % MOD * ifac[m] % MOD : 0; }

bool check() {
    int c1 = cnt[1], x = 0;
    vector<int> seg;
    queue<int> que;
    for (int i = 2; i <= N + 1; i++)
        for (int j = 1; j <= cnt[i]; j++)
            seg.push_back(i);
    for (int i = 1; i <= K; i++) {
        if (S[i] == 'r') {
            if (!seg.empty()) {
                que.push(seg.back());
                seg.pop_back();
            } else if (c1) {
                c1--;
            } else {
                x = max(0, x - 1);
            }
        } else {
            if (!que.empty()) {
                x += que.front() - 2;
                que.pop();
            } else {
                x = max(0, x - 1);
            }
        }
    }
    return x == 0 && c1 == 0 && seg.empty() && que.empty();
}

void solve() {
    if (!check()) {
        return;
    }
    int x = -1, y = 1, z = 0;
    ll c = 1;
    for (int i = 1; i <= N + 1; i++) {
        x += cnt[i] * max(2, i * 2 - 2);
        if (i != 1) y += cnt[i];
        z += cnt[i];
        (c *= comb(z, cnt[i])) %= MOD;
    }
    if (x == -1) {
        (ans += 1) %= MOD;
        return;
    }
    ll res = 0;
    for (int i = 0; i <= y * 2; i++) {
        (res += comb(N - 1, x + i - 1) * comb(y * 2, i)) %= MOD;
    }
    (ans += res * c) %= MOD;
}

void dfs(int x, int y) {
    if (y == N + 2) {
        solve();
        return;
    }
    int len = max(2, 2 * y - 2);
    for (int j = 0; x + len * j <= N; j++) {
        cnt[y] = j;
        dfs(x + len * j, y + 1);
    }
}

int main() {
    fac[0] = 1;
    for (int i = 1; i < MAX_N; i++) fac[i] = fac[i - 1] * i % MOD;
    ifac[MAX_N - 1] = inv(fac[MAX_N - 1]);
    for (int i = MAX_N - 1; i; i--) ifac[i - 1] = ifac[i] * i % MOD;
    scanf("%d%d", &N, &K);
    scanf("%s", S + 1);
    dfs(-1, 1);
    printf("%lld\n", ans);
}