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 long long ll;
const int N=205,mod=1e9+7;
ll ans,f[N],invf[N];
ll C(int n,int m)
{
    return f[n]*invf[n-m]%mod*invf[m]%mod;
}
int n,k,tot,cnt,pos[N],l[N],p[N],vv[N];
char s[N];
bool vis[N];
bool check()
{
    memset(vis,false,sizeof(vis[0])*(k+3));
    memset(vv,0,sizeof(vv[0])*(k+3));
    if(cnt>tot) return false;
    int j=1;
    for(int i=cnt;i>=1;i--)
    {
        int x=pos[j++];
        vis[x]=true;
        if(l[i]>=2)
        {
            if(!p[x]) return false;
            vis[p[x]]=true;
            vv[p[x]]=i;
        }
        else vv[x]=i;
    }
    int sum=0;
    for(int i=k;i>=1;i--)
        if(!vis[i]) sum++;
        else if(vv[i])
        {
            int x=max(0,l[vv[i]]-2);
            if(sum<x) return false;
            sum-=x;
        }
    return true;
}
bool dfs(int mn,int dep,int len)
{
    cnt=dep;
    if(!check()) return false;
    int s=dep+1;
    for(int i=1;i<=dep;i++)
        if(l[i]==1) s++;
    else s+=2*(l[i]-1)-1+2;
    ll res=C(n-len+s-1,s-1)*f[dep]%mod;
    int t=1;
    for(int i=2;i<=dep;i++)
        if(l[i]!=l[i-1]) res=res*invf[t]%mod,t=1;
    else t++;
    res=res*invf[t]%mod;
    ans=(ans+res)%mod;
    if(dep+1>tot) return true;
    for(int i=mn;i<=k;i++)
    {
        int nlen=len;
        if(dep!=0) nlen++;
        if(i<=2) nlen++;
        else nlen+=2*(i-1)-1;
        if(nlen>n) break;
        l[dep+1]=i;
        if(!dfs(i,dep+1,nlen)) break;
    }
    return true;
}
int main()
{
    f[0]=invf[0]=f[1]=invf[1]=1;
    for(int i=2;i<N;i++) f[i]=f[i-1]*i%mod,invf[i]=(mod-mod/i)*invf[mod%i]%mod;
    for(int i=2;i<N;i++) invf[i]=invf[i-1]*invf[i]%mod;
    scanf("%d%d",&n,&k);
    scanf("%s",s+1);
    for(int i=1;i<=k;i++)
        if(s[i]=='r')
    {
        pos[++tot]=i;
        for(int j=i+1;j<=k;j++)
            if(!vis[j]&&s[j]=='b')
        {
            p[i]=j;vis[j]=true;break;
        }
    }
    dfs(1,0,0);
    printf("%lld\n",ans);
}