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;
using lint = long long int;
constexpr lint MOD = 1000000007;

vector<lint> fac, facInv, inv;

void facInit(int nmax)
{
    fac = facInv = inv = vector<lint>(nmax + 1, 1);
    for (int i = 2; i <= nmax; i++)
    {
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        facInv[i] = facInv[i-1] * inv[i] % MOD;
    }
}

lint nCr(int n, int r)
{
    if (n<r || r<0) return 0;
    return (fac[n] * facInv[r] % MOD) * facInv[n-r] % MOD;
}

int N, K;
string s;

bool is_partition_able(vector<int> partition)
{
    int r_head = 0, b_head = 0;
    int pending = 0;
    for (auto c : s)
    {
        if (c == 'r')
        {
            if (r_head < partition.size()) r_head++;
            else pending = max(pending-1, 0);
        }
        else
        {
            if (r_head == b_head || partition[b_head] < 2) pending = max(pending-1, 0);
            else
            {
                pending += partition[b_head] - 2;
                b_head++;
            }
        }
    }
    if (pending > 0 || (b_head < partition.size() && partition[b_head] > 1) || r_head < partition.size()) return false;
    return true;
}


lint calc_for_each_partition(vector<int> &partition)
{
    if (!is_partition_able(partition)) return 0;

    int rd = 0;
    map<int, int> len_map;
    for (auto v : partition)
    {
        len_map[v]++;
        if (v > 1) rd += 2;
    }
    lint ans = nCr(N + 1 + rd, 2 * accumulate(partition.begin(), partition.end(), 0));
    for (auto v : len_map) (ans *= facInv[v.second]) %= MOD;
    (ans *= fac[partition.size()]) %= MOD;
    return ans;
}


lint dfs(vector<int> partition_now)
{
    lint ans = calc_for_each_partition(partition_now);
    int used_len = 0;
    for (auto v : partition_now) used_len += 1 + max(v*2-3, 1);
    // for (auto v : partition_now) used_len += v;
    int highest = partition_now.back();

    partition_now.push_back(0);

    if (partition_now.size() - 1 < K) for (int l=1; l<=min(highest, N-used_len); l++)
    {
        partition_now.back() = l;
        ans += dfs(partition_now);
    }
    return ans % MOD;
}


// r -> b -> (n個のrまたはb)で島を作る

int main()
{
    cin >> N >> K >> s;
    facInit(70*3);

    lint ans = 1;
    for (int i=1; i<=K; i++)
    {
        (ans += dfs(vector<int>{i})) %= MOD;
    }
    cout << ans << endl;
}