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 <iostream>
using namespace std;
int N, K;
char S[75];
int Fact[75], Inv[75];
int W[75][75][75];
bool Use[75];
const int MOD = 1000000007;
int F[75], R[75], B[75];
int V[75];
int ind, sum = 0, x[75], sumG, prod = 1;
int ans;
int powerLog(int n, int p)
{
    int sol = 1;
    while(p)
    {
        if(p % 2 == 1)
            sol = (1LL * sol * n) % MOD;
        p /= 2;
        n = (1LL * n * n) % MOD;
    }
    return sol;
}
void Read()
{
    cin >> N >> K;
    cin.get();
    cin.getline(S + 1, 75);
    Fact[0] = 1;
    for(int i = 1; i <= 70; i++)
        Fact[i] = (1LL * Fact[i - 1] * i) % MOD;
    Inv[70] = powerLog(Fact[70], MOD - 2);
    for(int i = 70 - 1; i >= 0; i--)
    {
        Inv[i] = (1LL * Inv[i + 1] * (i + 1)) % MOD;
    }
}
inline void Add(int& x, int y)
{
    x += y;
    if(x >= MOD)
        x -= MOD;
}
int Comb(int n, int k)
{
    if(k > n)
        return 0;
    if(k == -1 && n == -1)
        return 1;
    if(k == -1)
        return 0;
    return (((1LL * Fact[n] * Inv[n - k]) % MOD) * Inv[k]) % MOD;
}
void precalcWays()
{
    for(int fixed = 0; fixed <= 70; fixed++)
    {
        for(int fixed2 = 0; fixed2 <= 70; fixed2++)
        for(int b = 0; b <= 70; b++)
        {
            for(int r = 0; r + b <= 70; r++)
            {
                Add(W[fixed][fixed2][b + r], (1LL * Comb(r + fixed2 - 1, fixed2 - 1) * Comb(fixed + b - 1, fixed - 1) % MOD));
            }
        }
    }
}

bool check(int ind)
{
    //sort(F + 1, F + ind + 1);
    for(int i = 1; i <= K; i++)
        Use[i] = 0;
    int r = 1, b = 1;
    for(int i = ind; i >= 1; i--)
    {
        while(r <= K && S[r] != 'r')
            r++;

        if(r>= K + 1)
            return 0;
        R[i] = r;
        Use[r] = 1;
        ++r;
        if(F[i] >= 2)
        {
            b = max(b, R[i] + 1);
            while(b <= K && S[b] != 'b')
                ++b;

            if(b >= K + 1)
                return 0;
            B[i] = b;
            Use[b] = 1;
            ++b;
        }
    }
    int p = 1;
    for(int i = ind; i >= 1; i--)
    {
        if(F[i] >= 3)
        {
            int nb = F[i] - 2;
            p = max(p, B[i] + 1);
            while(nb > 0 && p <= K)
            {
                if(Use[p] == 0)
                {
                    nb--;
                    Use[p] = 1;
                }
                ++p;
            }
            if(nb > 0)
                return 0;
        }
    }
    return 1;
}
inline int Val(int x)
{
    if(x == 1)
        return 1;
    return (x - 1) * 2 - 1;
}
void genPartition(int k)
{
    for(int i = F[k - 1]; Val(i) + sum <= N; i++)
    {
        F[k] = i;
        sum += Val(i);
        sumG += F[k];
        prod = Fact[k];
        int cnt = 0;
        for(int j = 1; j <= F[k]; j++)
            V[j] = 0;
        for(int j = 1; j <= k; j++)
        {
            V[F[j]]++;
        }

        for(int j = 1; j <= F[k]; j++)
            prod = (1LL * Inv[V[j]] * prod) % MOD;
        int fixed = sumG - k;
        int fixed2 = fixed + k;
        /*if(fixed == 0)
            --fixed2;*/
        if(check(k))
        {
            for(int j = k - 1; j + sum <= N; j++)
            {
                int rem = N - j - sum;
                int w = j - k + 1;
                int aux = (1LL * W[fixed][fixed2][rem] * Comb(w + k, k)) % MOD;
                Add(ans, (1LL * aux * prod) % MOD);

            }
            genPartition(k + 1);
        }

        sum -= Val(i);
        sumG -= F[k];
    }
}
int main()
{
    F[0] = 1;
    Read();
    precalcWays();
    genPartition(1);
    cout << ans + 1<< "\n";
    return 0;
}