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;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;
inline void add(int &a,int b){
    a+=b;
    if(a>=mod)a-=mod;
}
int mpow(int n,int m){
    int ret=1;
    while(m){
        if(m&1)ret=ret*n%mod;
        n=n*n%mod;
        m>>=1;
    }
    return ret;
}
const int FACT_SIZE=1111111;
int fact[FACT_SIZE];
int inv[FACT_SIZE];
struct fact_exec{
    fact_exec(){
        fact[0]=1;
        for(int i=1;i<FACT_SIZE;i++)fact[i]=fact[i-1]*i%mod;
        inv[FACT_SIZE-1]=mpow(fact[FACT_SIZE-1],mod-2);
        for(int i=FACT_SIZE-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
    }
}factexec;
int nCk(int n,int k){
    if(n<0|k<0||k>n)return 0;
    return fact[n]*inv[k]%mod*inv[n-k]%mod;
}
int nPk(int n,int k){
    if(n<0||k<0||k>n)return 0;
    return fact[n]*inv[n-k]%mod;
}


int N,K;
string S;

int r[111],b[111];
int R,B;

int ans;
vint X;

bool used[100];
int p[100];
int calc(){
    int n=X.size();
    if(n>R)return 0;

    memset(used,0,sizeof(used));
    for(int i=0;i<n;i++)used[r[R-i]]=true;
    rep(i,n){
        if(X[i]==1)break;
        int pos=r[R-i]+1;
        while(pos<K&&(S[pos]=='r'||used[pos]))pos++;
        if(pos==K)return 0;
        used[pos]=true;
        p[i]=pos;
    }
    rep(i,n){
        if(X[i]<=2)break;
        int pos=p[i];
        rep(t,X[i]-2){
            while(pos<K&&used[pos])pos++;
            if(pos==K)return 0;
            used[pos]=true;
            pos++;
        }
    }

    /*
    rep(i,n)used[r[R-i]]=true;
    int pos=B;
    for(int i=0;i<n;i++){
        if(X[i]==1)break;
        while(pos>0&&b[pos]<r[R-i])pos--;
        if(pos==0)return 0;
        used[b[pos]]=true;
        p[i]=pos;
        pos--;
    }
    pos=0;
    rep(i,n){
        chmax(pos,b[p[i]]+1);
        rep(t,X[i]-2){
            while(pos<N&&used[pos])pos++;
            if(pos==N)return 0;
            used[pos]=true;
            pos++;
        }
    }

    */

    vpint ei;
    rep(i,X.size()){
        if(ei.size()==0||ei.back().fi!=X[i])ei.pb({X[i],1});
        else ei.back().se++;
    }

    int latte=0;
    int s=0;
    for(int i=0;i<X.size();i++){
        if(X[i]==1){
            latte++;
            s++;
        }
        else{
            latte+=X[i]*2-3;
            s+=X[i]*2-3+2;
        }
    }

    int ret=0;
    for(int k=0;latte+k<=N;k++){
        int y=N-latte-k;
        add(ret,nCk(y+1,n)*nCk(s-1+k,k)%mod);

    }
    ret=ret*fact[n]%mod;
    rep(i,ei.size())ret=ret*inv[ei[i].se]%mod;
    return ret;
}

void dfs(int n,int k){
    add(ans,calc());

    if(X.size()>=R)return;
    for(int i=1;i<=X.back();i++){
        int nn=n+1;
        if(i==1)nn++;
        else nn+=2*i-3;
        int nk=k+i;
        if(nn>N||nk>K)continue;
        X.pb(i);
        dfs(nn,nk);
        X.pop_back();
    }
}

signed main(){
    cin>>N>>K;
    cin>>S;
    for(int i=K-1;i>=0;i--){
        if(S[i]=='r'){
            r[++R]=i;
        }
        else{
            b[++B]=i;
        }
    }

    for(int i=1;i<=K;i++){
        X.pb(i);
        if(i==1)dfs(1,1);
        else dfs(2*i-3,i);
        X.pop_back();
    }
    add(ans,1ll);
    cout<<ans<<endl;
    return 0;
}