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>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;


string str;
ll comb[301][301];
int n,k;
int group[81];
int assign[81];
bool used[81];
ll dp2[101][101];
ll ans;

bool isvalid(int v){
	int len=0;
	for(int i=0;i<v;i++){
		if(i!=0)len++;
		if(group[i]==1){
			len++;
		}else{
			len+=group[i]*2-3;
		}
	}
	if(len>n)return false;
	memset(assign,0,sizeof(assign));
	memset(used,false,sizeof(used));
	int cnt=0;
	for(int i=0;i<k;i++){
		if(cnt==v)break;
		if(str[i]=='r'){
			assign[cnt++]=i;
			used[i]=true;
		}
	}
	if(cnt<v)return false;
	for(int i=0;i<v;i++){
		if(group[i]>=2){
			bool flag=false;
			for(int j=assign[i]+1;j<k;j++){
				if(str[j]=='b' && !used[j]){
					assign[i]=j;
					used[j]=true;
					flag=true;
					break;
				}
			}
			if(!flag)return false;
		}
	}
	for(int i=0;i<v;i++){
		if(group[i]>=3){
			int rest=group[i]-2;
			for(int j=assign[i]+1;j<k;j++){
				if(!used[j]){
					used[j]=true;
					rest--;
				}
				if(rest==0)break;
			}
			if(rest!=0)return false;
		}
	}
	return true;
}

ll dp[2][71];

void dfs(int v,int now){
	if(v>0){
		if(!isvalid(v))return;
		memset(dp,0,sizeof(dp));
		int cur=0,nxt=1;
		dp[cur][v-1]=1;
		for(int i=0;i<v;i++){
			for(int j=0;j<=n;j++){
				if(group[i]==1){
					if(j+1<=n){
						dp[nxt][j+1]+=dp[cur][j];
						dp[nxt][j+1]%=MOD;
					}
				}else{
					int pl=(group[i]-1)*2-1;
					if(j+pl<=n){
						dp[nxt][j+pl]+=dp[cur][j];
						dp[nxt][j+pl]%=MOD;
					}
					pl=(group[i]-1)*2;
					if(j+pl<=n){
						dp[nxt][j+pl]+=dp[cur][j]*2LL;
						dp[nxt][j+pl]%=MOD;
					}
					pl=(group[i]-1)*2+1;
					if(j+pl<=n){
						dp[nxt][j+pl]+=dp[cur][j];
						dp[nxt][j+pl]%=MOD;
					}
				}
			}
			swap(cur,nxt);
			memset(dp[nxt],0,sizeof(dp[nxt]));
		}
		/*
		for(int i=0;i<v;i++){
			printf("%d ",group[i]);
		}
		printf("ok\n");
		*/
		ll pw=1;
		int len=1,rest=v;
		for(int i=1;i<v;i++){
			if(group[i]==group[i-1]){
				len++;
			}else{
				pw=pw*comb[rest][len]%MOD;
				rest-=len;
				len=1;
			}
		}

		for(int i=1;i<=n;i++){
			ll va=(dp[cur][i]*pw)%MOD;
			//printf("%lld ",dp[cur][i]);
			va=va*dp2[i+2][n-i]%MOD;
			ans+=va;
			ans%=MOD;
		}
		//printf("\n");
		//printf("%lld %lld\n",pw,ans);
	}
	for(int i=1;i<=now;i++){
		group[v]=i;
		dfs(v+1,i);
	}
}

int main(void){
	comb[0][0]=1;
	for(int i=1;i<=300;i++){
		for(int j=1;j<i;j++){
			comb[i][j]=(comb[i-1][j-1]+comb[i-1][j])%MOD;
		}
		comb[i][0]=1;
		comb[i][i]=1;
	}
	dp2[1][0]=1;
	for(int i=0;i<100;i++){
		for(int j=0;j<100;j++){
			dp2[i+1][j]+=dp2[i][j];
			dp2[i+1][j]%=MOD;
			dp2[i][j+1]+=dp2[i][j];
			dp2[i][j+1]%=MOD;
		}
	}
	scanf("%d%d",&n,&k);
	cin >> str;
	dfs(0,38);
	printf("%lld\n",(ans+1LL)%MOD);
	return 0;
}