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 pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int cys=1000000007;
int n,k,cnt; ll ans=1;
ll fac[155],inv[155],f[75],nxt[75][2],now[2],a[75],b[75];
char s[75];
bool vis[75];

ll mod(ll x){return x>=cys?x-cys:x;}
ll C(ll x,ll y){return x<y?0:fac[x]*inv[y]%cys*inv[x-y]%cys;}

ll qpow(ll x,ll p){
	ll ret=1;
	for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys;
	return ret;
}

ll getans(){
	memset(vis,0,sizeof(vis));
	int pl=0,num=0;
	for(int i=1;i<=cnt;i++) if(f[i]==1) num++;
	for(int i=1;i<=cnt;i++){
		pl=nxt[pl][0];
		if(pl>k) return 0;
		a[i]=pl,vis[pl]=1;
	}
	for(int i=1;i<=cnt-num;i++){
		int tmp=nxt[a[i]][1];
		while(vis[tmp]) tmp=nxt[tmp][1];
		if(tmp>k) return 0;
		b[i]=tmp,vis[tmp]=1;
	}
	int now=cnt-num,pcnt=f[now];
	while(f[now]==2) now--,pcnt=f[now];
	for(int i=k;i>=1;i--){
		if(vis[i]) continue;
		if(i<b[now]) return 0;
		pcnt--;
		if(pcnt==2) now--,pcnt=f[now];
		if(!now) break;
	}
	if(pcnt>2) return 0;
	int rnum=num,bnum=0,wnum=cnt-1,all=n;
	for(int i=1;i<=cnt-num;i++) rnum+=f[i]-2,bnum+=f[i]-1;
	all-=rnum+bnum+wnum;
	if(all<0) return 0;
	ll res=fac[cnt],lst=1;
	for(int i=1;i<=cnt;i++) if(f[i]!=f[i-1]&&i>1) res=res*inv[i-lst]%cys,lst=i;
	res=res*inv[cnt+1-lst]%cys;
	return res*C(all+rnum+bnum+wnum+(cnt-num)*2+1,rnum+bnum+wnum+(cnt-num)*2+1)%cys;
}

void dfs(int now,int sum,int all,bool tp){
	if(all>n) return;
	if(!tp) ans=mod(ans+getans());
	if(!sum||!now) return;
	for(int i=0;i<=sum/now;i++){
		dfs(min(now-1,sum-i*now),sum-i*now,all+i*(now==1?1:2*now-3),i==0?1:0);
		f[++cnt]=now;
	}
	cnt-=sum/now+1;
}

int main(){
	n=readint(); k=readint();
	fac[0]=inv[0]=1;
	for(int i=1;i<=150;i++) fac[i]=fac[i-1]*i%cys;
	inv[150]=qpow(fac[150],cys-2);
	for(int i=149;i>=1;i--) inv[i]=inv[i+1]*(i+1)%cys;
	scanf("%s",s+1);
	now[0]=now[1]=k+1;
	for(int i=k;i>=0;i--){
		nxt[i][0]=now[0],nxt[i][1]=now[1];
		if(s[i]=='r') now[0]=i;
		else now[1]=i;
	}
	dfs(k,k,0,1);
	printf("%lld\n",ans);
	return 0;
}