Problem:


Score : 1100 points

Problem Statement

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.

Sample Input 1

2 2
rb

Sample Output 1

9

There are nine possible sequences of colors of the balls, as follows:

ww, wr, rw, rr, wb, bw, bb, rb, br.

Here, r represents red, b represents blue and wrepresents white.

Sample Input 2

5 2
br

Sample Output 2

16

Since we cannot directly paint white balls in blue, we can only choose an empty segment in the first operation.

Sample Input 3

7 4
rbrb

Sample Output 3

1569

Sample Input 4

70 70
bbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr

Sample Output 4

841634130



Sample input:
2 2
rb


Sample output:
9

Submission status: Runtime Error

Solution code:
#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);
    int highest = partition_now.back();

    partition_now.push_back(0);

    if (partition_now.size() - 1 < K) for (int l=1; l<=min(highest, K-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;
}