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>
#define FOR(i, l, r) for(int i = l; i <= r; ++i)

using namespace std;

#define left LEFT
typedef long long ll;
const int N = 510;
const int mod = 1e9 + 7;

int n, k, ans, tot, left, a[N], c[N][N];
char s[N];

bool check()
{
    if (!tot) return 0;
    int now1 = 1, now2 = 1, c = 0;
    FOR(i, 1, k)
    {
        if (!(now1 <= tot || a[now2] > 1 || c)) break;
        if (now1 <= tot && s[i] == 'r') ++now1; else
        if (now2 < now1 && a[now2] > 1 && s[i] == 'b') c += a[now2++] - 2;
        else if (c) --c;
    }
    return !(now1 <= tot || a[now2] > 1 || c);
}

void update()
{
    ll tmp = 1, num = tot + 1;
    for(int i = 1, j; i <= tot; i = j + 1)
    {
        for(j = i; a[j + 1] == a[i]; ++j);
        tmp = tmp * c[j][i - 1] % mod;
        num += (j - i + 1) * (a[i] * 2 - 1);
    }
    tmp = tmp * c[num + left - 1][num - 1] % mod;
    if ((ans += tmp) >= mod) ans -= mod;
}

void dfs(int mx)
{
    if (left < 0) return;
    if (check()) update();

    if (tot) --left;
    ++tot; --left; dfs(a[tot] = 1); ++left;
    FOR(i, 2, mx)
    {
        left -= i * 2 - 3;
        dfs(a[tot] = i);
        left += i * 2 - 3;
    }
    a[tot--] = 0;
    if (tot) ++left;
}

int main()
{
    FOR(i, 0, 500)
    {
        c[i][0] = 1;
        FOR(j, 1, 500)
            if ((c[i][j] = c[i - 1][j] + c[i - 1][j - 1]) >= mod)
                c[i][j] -= mod;
    }

    scanf("%d%d%s", &n, &k, s + 1);
    left = n; dfs(100);
    printf("%d\n", (ans + 1) % mod);
    return 0;
}