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;

typedef pair<int, int> pii;

const int mod = 1e9 + 7;

int exp(int x, int n) {
    int ret = 1;
    while(n) {
        if(n & 1) ret = 1LL * ret * x % mod;
        x = 1LL * x * x % mod;
        n >>= 1;
    }
    return ret;
}
int inv(int x) {
    return exp(x, mod - 2);
}
int fact[500], invf[500];

int comb(int n, int k) {
    return 1LL * fact[n] * invf[k] % mod * invf[n - k] % mod;
}
int H(int n, int k) {
    return comb(n + k - 1, k);
}

int N, K;
string S;
vector<int> R, B;

struct Group {
    vector<int> f;
};
vector<Group> group;
Group tmp;

void dfs(int p, int g, int f) {
    if(p >= N) {
        group.push_back(tmp);
        return;
    }
    if(f) {
        group.push_back(tmp);
    }
    if(max(p + 2*g, p + 2) > N + 1) return;

    dfs(p, g + 1, 0);

    if(max(p + 2*g, p + 2) <= N + 1) {
        tmp.f.push_back(g);
        dfs(max(p + 2*g, p + 2), g, 1);
        tmp.f.pop_back();
    }
}

bool chk(vector<int> &f) {
    vector<int> used(K, 0);
    vector<pii> bpos;

    int pos1 = 0, pos2 = 0;
    for(int i = (int)f.size() - 1; i >= 0; i--) {
        if(f[i] == 0) continue;

        while(pos2 < B.size() && R[pos1] > B[pos2]) pos2++;

        if(pos2 == B.size()) return false;
        bpos.push_back(pii(B[pos2], f[i] - 1));

        used[ R[pos1] ] = 1;
        used[ B[pos2] ] = 1;

        pos1++;
        pos2++;
    }
    for(int i = 0; i < f.size(); i++) {
        if(f[i]) continue;
        
        for(int j = 0; j < K; j++) if(!used[j] && S[j] == 'r') {
            used[j] = 1;
            break;
        }
    }
    
    for(int i = (int)bpos.size() - 1; i >= 0; i--) {
        int need = bpos[i].second;
        int pos = bpos[i].first;

        for(int j = pos + 1; j < K; j++) {
            if(need == 0) break;
            if(!used[j]) {
                need--;
                used[j] = 1;
            }
        }
        if(need) return false;
    }

    return true;
}

int main() {
    fact[0] = 1;
    for(int i = 1; i < 500; i++) {
        fact[i] = 1LL * fact[i - 1] * i % mod;
    }
    for(int i = 0; i < 500; i++) {
        invf[i] = inv(fact[i]);
    }

    cin >> N >> K >> S;

    for(int i = 0; i < S.size(); i++) {
        if(S[i] == 'r') R.push_back(i);
        else B.push_back(i);
    }

    dfs(0, 0, 1);

    int ans = 0;
    for(int g = 0; g < group.size(); g++) {
        vector<int> f = group[g].f;

        int sum = 0;
        int x = 0;
        for(int i = 0; i < f.size(); i++) {
            sum += f[i];

            if(f[i] == 0) x++;
            else x += 2*f[i] - 1;
        }

        if(f.size() > R.size()) continue;
        if(sum + f.size() > K) continue;

        int t = fact[ f.size() ];

        int cnt = 0;
        for(int i = 0; i < f.size(); i++) {
            cnt++;
            if(i == f.size() - 1 || f[i] != f[i + 1]) {
                t = 1LL * t * invf[cnt] % mod;
                cnt = 0;
            }
        }

        t = 1LL * t * H(2*sum + 2*f.size() + 1, N - x - (int)f.size() + 1) % mod;

        if(chk(f)) {
            ans += t;
            ans %= mod;
        }
    }

    cout << ans;
}