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;

int cnt = 0, N, K, fac[109], inv[109], c[109][109], cntRB[109][109], cntWRB[109][109], oldDp[109], currDp[109], ways[420009];
char sir[109];
bool dp[420009];
vector < int > curr, arrs[420009], edge[420009][2];
vector < pair < int, int > > sons[420009];
map < vector < int >, int > mp;
vector < int > cc[2];
const int mod = 1e9 + 7;

int add (int x, int y) {int ans = x + y; if (ans >= mod) ans -= mod; return ans;}
int subtract (int x, int y) {if (x >= y) return x - y; return x - y + mod;}
int mul (int x, int y) {return 1LL * x * y % mod;}
void adto (int &x, int y) {x += y; if (x >= mod) x -= mod;}

int power (int a, int b)
{
    int p = 1;
    for (int i=0; (1<<i) <= b; i++)
    {
        if (b & (1 << i)) p = mul (p, a);
        a = mul (a, a);
    }
    return p;
}

void back (int lst, int sum, int papa)
{
    if (sum <= N)
    {
        /*for (auto j : curr)
            printf ("%d ", j);
        printf ("\n");*/
        mp[curr] = ++cnt, arrs[cnt] = curr;
        sons[papa].push_back ({cnt, lst});
    }
    if (sum > N) return ;
    int aux = cnt;
    for (int i=lst;; i++)
    {
        int ad = (curr.empty () ? 0 : 1) + (i == 0 ? 1 : 2 * i - 1);
        if (ad + sum > N) break;
        curr.push_back (i), back (i, sum + ad, aux);
        curr.erase (curr.begin () + curr.size () - 1);
    }
}

void print (int id, string s) {printf ("[");for (auto j : arrs[id]) printf ("%d", j); printf ("]%s", s.c_str ());}

void buildTransitionGraph ()
{
    for (int id = 1; id <= cnt; id ++)
        for (int type = 0; type < 2; type ++)
        {
            if (type == 0)
            {
                ///Red, add 0 or increase non zero by 1
                vector < int > curr;
                curr.push_back (0);
                for (auto it : arrs[id])
                    curr.push_back (it);
                if (mp.count (curr))
                    edge[id][type].push_back (mp[curr]);

                curr = arrs[id];
                for (int i=0; i<curr.size (); i++)
                    if ((i == curr.size () - 1 || curr[i] != curr[i + 1]) && curr[i] > 0)
                    {
                        curr[i] ++;
                        if (mp.count (curr))
                            edge[id][type].push_back (mp[curr]);
                        curr[i] --;
                    }
            }
            else
            {
                ///Blue, add 1 to anything
                vector < int > curr = arrs[id];
                for (int i=0; i<curr.size (); i++)
                    if (i == curr.size () - 1 || curr[i] != curr[i + 1])
                    {
                        curr[i] ++;
                        if (mp.count (curr))
                            edge[id][type].push_back (mp[curr]);
                        curr[i] --;
                    }
            }
        }
/*    for (int id = 1; id<=cnt; id++)
    {
        print (id, ": ");
        for (int type = 0; type < 2; type ++, printf (" | "))
            for (auto j : edge[id][type])
                print (j, ", ");
        printf ("\n");
    }*/
}

void buildDp ()
{
    dp[1] = 1;
    cc[0].push_back (1), cc[1].push_back (1);
    for (int i=1; i<=K; i++)
    {
        int type = (sir[i] == 'b');
        vector < int > newCC;
        for (auto j : cc[type])
            for (auto k : edge[j][type])
                if (dp[k] == 0)
                    dp[k] = 1, newCC.push_back (k);
        cc[type].clear ();
        for (int j=0; j<2; j++)
            for (auto k : newCC)
                cc[j].push_back (k);
    }
}

void binomialCoefficients ()
{
    c[0][0] = 1;
    for (int i=1; i<=100; i++)
    {
        c[i][0] = 1;
        for (int j=1; j<=i; j++)
            c[i][j] = add (c[i - 1][j - 1], c[i - 1][j]);
    }
    fac[0] = 1;
    for (int i=1; i<=100; i++)
        fac[i] = mul (fac[i - 1], i);
    for (int i=0; i<=100; i++)
        inv[i] = power (fac[i], mod - 2);
}

void computeCntRB ()
{
    for (int l=1; l<=N; l++)
    {
        cntRB[l][0] = 1;
        for (int i=1; 2 * i - 1 <= l; i++)
            cntRB[l][i] = c[l + 1][2 * i];
    }
    for (int l=1; l<=N; l++)
        for (int j=0; j<=N; j++)
            for (int k=1; k<l; k++)
                adto (cntWRB[l][j], cntRB[l - k][j]);
}

int getCount (int id)
{
    if (id == 1) return 1;
    vector < int > curr = arrs[id];
    ///compute dp
    /*for (int i=1; i<=N; i++)
        currDp[i] = add (cntWRB[i][curr[0]], cntRB[i][curr[0]]);///can even have no white
    for (int currStep = 1; currStep < curr.size (); currStep ++)
    {
        int l = curr[currStep];
        memcpy (oldDp, currDp, sizeof (currDp));
        memset (currDp, 0, sizeof (currDp));
        for (int i=1; i<=N; i++)
            if (oldDp[i] != 0)
                for (int j=2 * l; i + j<=N; j++)
                    adto (currDp[i + j], mul (oldDp[i], cntWRB[j][l]));///must have a white to separate
    }*/
    ///number of anagrams
    int prms = fac[curr.size ()];
    for (int i=0; i<curr.size (); i++)
    {
        int j;
        for (j=i; j<curr.size (); j++)
            if (curr[j] != curr[i]) break;
        j --;
        ///[i, j]
        prms = mul (prms, inv[j - i + 1]);
        ///
        i = j;
    }
    return mul (ways[id], prms);
}

void dfs (int node)
{
    if (node == 1)
    {
        for (auto pp : sons[node])
        {
            int l = pp.second, id = pp.first;
            for (int i=1; i<=N; i++)
                currDp[i] = add (cntWRB[i][l], cntRB[i][l]);///can even have no white
            dfs (id);
        }
        return ;
    }
    int oldDp[109];
    memcpy (oldDp, currDp, sizeof (currDp));
    for (auto pp : sons[node])
        {
            int l = pp.second, id = pp.first;
            memset (currDp, 0, sizeof (currDp));
            for (int i=1; i<=N; i++)
                if (oldDp[i] != 0)
                    for (int j=2 * l; i + j<=N; j++)
                        adto (currDp[i + j], mul (oldDp[i], cntWRB[j][l]));///must have a white to separate
            dfs (id);
            memcpy (currDp, oldDp, sizeof (oldDp));
        }
    ways[node] = 0;
    for (int i=1; i<=N; i++)
        adto (ways[node], currDp[i]);
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d\n", &N, &K);
scanf ("%s", sir + 1);
back (0, 0, 0);
buildTransitionGraph ();
buildDp ();
binomialCoefficients ();
computeCntRB ();
dfs (1);
int ans = 0;
for (int i=1; i<=cnt; i++)
    if (dp[i])
    {
        int curr = getCount (i);
//        print (i, " -> "), printf ("%d\n", curr);
        adto (ans, curr);
    }
printf ("%d\n", ans);
return 0;
}