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;
const int mod=1e9+7;
void ade(int& x,int y){x+=y;if(x>=mod)x-=mod;}
int add(int x,int y){return x+y<mod?x+y:x+y-mod;}
int qpow(int x,int k)
{
    int r=1;
    while(k)
    {
        if(k&1)r=1ll*r*x%mod;
        k>>=1;x=1ll*x*x%mod;
    }
    return r;
}
int C[1010][1010];
int fac[1010],ifac[1010];
void init()
{
    for(int i=0;i<=1000;++i)
    {
        C[i][0]=1;
        for(int j=1;j<=i;++j)C[i][j]=add(C[i-1][j],C[i-1][j-1]);
    }
    fac[0]=1;
    for(int i=1;i<=1000;++i)fac[i]=1ll*fac[i-1]*i%mod;
    ifac[1000]=qpow(fac[1000],mod-2);
    for(int i=999;i>=0;--i)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}
int n,m;
int tr;
char s[110];
int a[110];
bool book[77];
bool eb[77];
bool check(int d)
{
    int cr=0,crb=0;
    for(;a[cr+1]==1&&cr+1<=d;cr++);
    crb=d-cr;
    memset(book,0,sizeof(book[0])*(m+3));
    memset(eb,0,sizeof(eb[0])*(m+3));
    int pr=0,pb=0;
    for(int t=1;t<=crb;++t)
    {
        while((s[pr]!='r'||book[pr])&&pr<=m)pr++;
        while((s[pb]!='b'||book[pb]||pb<=pr)&&pb<=m)pb++;
        if(pr>m||pb>m)return 0;
        book[pr]=book[pb]=1;
        eb[pb]=1;
    }
    int tcr=cr;
    for(int i=1;i<=m&&cr;++i)
        if(!book[i]&&s[i]=='r')cr--,book[i]=1;
    if(cr)return 0;
    for(int i=m,p=tcr+1,cnt=0;p<=d;--i)
    {
        if(!book[i])cnt++;
        if(eb[i])
        {
            cnt-=a[p]-2;
            if(cnt<0)return 0;
            p++;
        }
    }
    return 1;
}
int ans;
void calc(int d,int l)
{
    int s=d+1;
    for(int i=1;i<=d;++i)
        if(a[i]==1)s++;
        else s+=(a[i]-1)*2+1;
    int res=1ll*C[n-l+s-1][s-1]*fac[d]%mod;
    for(int i=1,j;i<=d;i=j+1)
    {
        for(j=i;a[j+1]==a[i]&&j<d;++j);
        res=1ll*res*ifac[j-i+1]%mod;
    }
    ade(ans,res);
}
bool dfs(int x,int la,int len,int sl)
{
    if(!check(x-1))return 0;
    if(x-1>tr)return 1;
    calc(x-1,len);
    int nl;
    for(int i=la;i<=m-sl;++i)
    {
        a[x]=i;
        nl=len;
        if(x!=1)nl++;
        if(i==1)nl++;
        else nl+=(i-1)*2-1;
        if(nl>n)break;
        if(!dfs(x+1,i,nl,sl+i))break;
    }
    return 1;
}
int main()
{
    init();
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    for(int i=1;i<=m;++i)tr+=(s[i]=='r');
    dfs(1,1,0,0);
    printf("%d\n",ans);
    return 0;
}