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 long long mod=1000000007;
    const long long inf=mod*mod;
    const long long d2=(mod+1)/2;
    const double EPS=1e-6;
    const double PI=acos(-1.0);
    int ABS(int a){return max(a,-a);}
    long long ABS(long long a){return max(a,-a);}
    char in[110];
    int R[110];
    int bl[110];
    int used[110];
    int lim[110];
    int sz;
    long long C[210][210];
    long long fact[110];
    long long inv[110];
    long long finv[110];
    int now[110];
     
    long long dp[110][110][110];
    long long calc(int x,int y,int a){
    	for(int i=0;i<80;i++)for(int j=0;j<80;j++)for(int k=0;k<80;k++)dp[i][j][k]=0;
    	dp[0][0][0]=1;
    	int n=a-y-(x+y-1);
    	for(int i=0;i<n;i++){
    		for(int j=0;j<=x;j++){
    			for(int k=0;k<=n;k++){
    				if(!dp[i][j][k])continue;
    				for(int l=0;j+l<=x&&k+l*(2*i+1)<=n;l++){
    					if(l&&lim[x-l-j]<(k-j)/2+l*i)break;
    					dp[i+1][j+l][k+l*(2*i+1)]=(dp[i][j][k]*C[j+l+y][l]+dp[i+1][j+l][k+l*(2*i+1)])%mod;
    				}
    			}
    		}
    	}
    	long long ret=0;
    	for(int i=0;i<=n;i++){
    		ret=(ret+C[n+3*x+2*y][n-i]*dp[n][x][i])%mod;
    	}
    	//printf("%d %d %d: %lld\n",x,y,a,ret);
    	return ret;
    }
    int main(){
    	C[0][0]=1;
    	for(int i=0;i<205;i++){
    		for(int j=0;j<=i;j++){
    			C[i+1][j]=(C[i+1][j]+C[i][j])%mod;
    			C[i+1][j+1]=(C[i+1][j+1]+C[i][j])%mod;
    		}
    	}
    	int a,b;scanf("%d%d",&a,&b);
    	//n=a;
    	fact[0]=finv[0]=inv[1]=1;
    	for(int i=2;i<110;i++)inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
    	for(int i=1;i<110;i++){
    		fact[i]=fact[i-1]*i%mod;
    		finv[i]=finv[i-1]*inv[i]%mod;
    	}
    	scanf("%s",in);
    	long long ret=0;
    	for(int i=0;i<b;i++){
    		if(in[i]=='r'){
    			R[sz++]=i;
    		}
    	}
    	for(int i=0;i<=sz;i++){
    		for(int j=0;i+j<=sz;j++){
    			for(int k=0;k<b;k++)used[k]=lim[k]=0;
    			for(int k=0;k<i+j;k++)used[R[k]]=1;
    			bool dame=false;
    			for(int k=0;k<i;k++){
    				bool ok=false;
    				for(int l=R[k];l<b;l++){
    					if(!used[l]&&in[l]=='b'){
    						ok=true;used[l]=1;bl[k]=l;break;
    					}
    				}
    				if(!ok){dame=true;break;}
    			}
    			if(dame)continue;
    		//	printf("%d %d\n",i,j);
    			for(int k=0;k<i;k++){
    				for(int l=bl[k]+1;l<b;l++){
    					if(!used[l])lim[k]++;
    				}
    			}
     
    			ret=(ret+calc(i,j,a))%mod;
    		}
    	}
    	printf("%lld\n",ret);
    }