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

const int N = 71;
const int N2 = 36;
const int M = 200;
const int MOD = (int)1e9 + 7;

int fact[N], inv_fact[N], binom[M][M], n, m, dp[N2][N2];
char s[N];

void update(int& x, int a)
{
    x += a;
    if (x >= MOD) {
        x -= MOD;
    }
}

int main()
{
#ifdef LOCAL_JUDGE
    freopen("F.in", "r", stdin);
#endif
    fact[0] = inv_fact[0] = inv_fact[1] = 1;
    for (int i = 2; i < N; ++ i) {
        inv_fact[i] = 1LL * (MOD - MOD / i) * inv_fact[MOD % i] % MOD;
    }
    for (int i = 1; i < N; ++ i) {
        fact[i] = 1LL * i * fact[i - 1] % MOD;
        inv_fact[i] = 1LL * inv_fact[i] * inv_fact[i - 1] % MOD;
    }
    for (int i = 0; i < M; ++ i) {
        binom[i][0] = 1;
        for (int j = 1; j <= i; ++ j) {
            binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % MOD;
        }
    }
    scanf("%d%d%s", &n, &m, s);
    int result = 1;
    for (int ab = 0; ab * 2 <= m; ++ ab) {
        for (int a = !ab; ab * 2 + a <= m; ++ a) {
            std::vector<int> sz(ab);
            int cnt_ab = 0, cnt_a = 0;
            for (int i = 0; i < m; ++ i) {
                if (s[i] == 'r') { // A
                    if (cnt_ab + cnt_a < ab + a) {
                        cnt_a ++;
                    } else if (cnt_ab) {
                        sz[ab - cnt_ab] ++;
                    }
                } else {
                    if (cnt_a && cnt_ab < ab) {
                        cnt_a --;
                        cnt_ab ++;
                    } else if (cnt_ab) {
                        sz[ab - cnt_ab] ++;
                    }
                }
            }
            if (cnt_ab != ab || cnt_a != a) {
                continue;
            }
            for (int i = 1; i < ab; ++ i) {
                sz[i] += sz[i - 1];
            }
            memset(dp, 0, sizeof(dp));
            dp[0][0] = 1LL * fact[ab + a] * inv_fact[a] % MOD;
            for (int q = 0; 2 * q - 1 <= n; ++ q) {
                for (int cnt = ab; cnt >= 0; -- cnt) {
                    for (int used = (n + 1 >> 1) - cnt; used >= 0; -- used) {
                        for (int k = 1; cnt + k <= ab && (cnt + k + used + k * q << 1) - 1 <= n && used + k * q <= sz[cnt + k - 1]; ++ k) {
                            update(dp[cnt + k][used + k * q], 1LL * dp[cnt][used] * inv_fact[k] % MOD);
                        }
                    }
                }
            }
            for (int used = (n + 1 >> 1) - ab; used >= 0; -- used) {
                int parts = ab + a;
                int occ = (used * 2 + ab) + a + (parts - 1);
                int balls = n - occ;
                int boxes = (2 * used + 3 * ab) + a + (parts + 1);
                update(result, 1LL * binom[balls + boxes - 1][boxes - 1] * dp[ab][used] % MOD);
            }
        }
    }
    printf("%d\n", result);
}