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 <cstdio>
typedef long long ll;

const int P=1000000007;
int n,K,Ans,a[75],Fac[305],Inv[305];
char s[75];

inline int C(int n,int m){return (ll)Fac[n]*Inv[m]%P*Inv[n-m]%P;}

void Check(int num,int sum)
{
    int pos=num+1,res=Fac[num],rnum=0,leftr=0,nxt=0,left=0;
    for(int i=1;i<=K;++i)
        if(s[i]=='r') rnum<num?leftr+=(a[++rnum]>1):(left?--left:0);
        else leftr?(--leftr,left+=a[++nxt]-2):(left?--left:0);
    if(left||rnum<num||leftr) return;
    for(int i=1,j;i<=num;i=j+1)
    {
        for(j=i;j<num&&a[j+1]==a[i];++j);
        res=1LL*res*Inv[j-i+1]%P;
        pos+=(j-i+1)*(a[i]*2-1);
    }
    Ans=(Ans+1LL*res*C(n-sum+pos-1,pos-1))%P;
}
void DFS(int x,int num,int sum)
{
    if(sum>n) return;Check(num,sum);
    for(int i=x;i;--i) a[num+1]=i,DFS(i,num+1,sum+(i>1?i*2-3:1)+(num>0));
}

int main()
{
    scanf("%d%d%s",&n,&K,s+1),Fac[0]=Inv[0]=Fac[1]=Inv[1]=1;
    for(int i=2;i<=300;++i)Fac[i]=(ll)Fac[i-1]*i%P,Inv[i]=ll(P-P/i)*Inv[P%i]%P;
    for(int i=2;i<=300;++i)Inv[i]=(ll)Inv[i-1]*Inv[i]%P;
    return DFS(70,0,0),printf("%d\n",Ans),0;
}