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;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,u) for(int i=start[u];i;i=e[i].next)
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
#define SZ(A) ((int)A.size())
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
inline void myassert(bool a,string s){ if(!a)cerr<<s<<endl,exit(0);}
inline int read()
{
	int s=0,f=1;char ch=getchar();
	while(!isdigit(ch) && ch!='-')ch=getchar();
	if(ch=='-')ch=getchar(),f=-1;
	while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
	return ~f?s:-s;
}

const int mod=1e9+7;
const int maxn=400;

int C[maxn][maxn],jc[maxn],jcn[maxn],inv[maxn];

int n,k;
char str[maxn];

int len;
int rk[maxn],tp;

inline void init()
{
	C[0][0]=1; REP(i,1,300)REP(j,0,i)C[i][j]=(C[i-1][j]+(j?C[i-1][j-1]:0))%mod;
	jc[0]=jc[1]=jcn[0]=jcn[1]=inv[1]=1;
	REP(i,2,300)jc[i]=(ll)i*jc[i-1]%mod,inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod,jcn[i]=(ll)jcn[i-1]*inv[i]%mod;
	n=read();k=read(); len=n+1>>1;
	scanf("%s",str+1);
	REP(i,1,k)if(str[i]=='r')rk[++tp]=i;
}

int p[maxn];
int tot;
int wp[maxn],B[maxn];

inline bool check()
{
	static int vis[maxn],RK[maxn];
	memset(vis,0,sizeof(int)*(k+1));

	int now=0,num=0;
	DREP(i,tot,0)num+=p[i];
	if(num>tp)return 0;
	REP(i,1,num)vis[rk[i]]=1;

	int it=1;
	DREP(i,tot,0)
	{
		REP(j,1,p[i])
		{
			int x=rk[++now];
			if(i>=1)
			{
				while(it<=k && (it<=x || vis[it] || str[it]=='r'))++it;
				if(it>k)return 0;
				RK[now]=it;
				vis[it]=1;
			}else RK[now]=x;
		}
	}

	now=0;
	it=1;
	DREP(i,tot,0)
	{
		int NUM=p[i];
		while(NUM--)
		{
			int x=RK[++now];
			int tim=i-1;
			if(i>=2)
			{
				while(tim--)
				{
					while(it<=k && (it<=x || vis[it] ))++it;
					if(it>k)return 0;
					vis[it]=1;
				}
			}
		}
	}
	return 1;
}

int ans;

void dfs(int u,int num,int s,int wz,int N,int pro)
{
	if(u==-1)
	{
		pro=(ll)pro*jc[num]%mod;
		wz++; N+=2;
		//DREP(i,len,0)pro=(ll)pro*jcn[p[i]]%mod;
		ans=(ans+(ll)pro*C[N-1][wz-1])%mod;
		return;
	}
	//int ad=u%4==0?2:u%4==1?0:1;
	REP(j,0,(n-s+1)/(wp[u]+1))
	{
		p[u]=j;
		if(num+j<=tp && check())
			dfs(u-1,num+j,s+j*wp[u]+j,wz+wp[u]*j+j+(u>0?2*j:0),N+(u>0?2*j:0),(ll)pro*jcn[j]%mod);
		p[u]=0;
	}
}

inline void doing()
{
	wp[0]=1;
	REP(i,1,len)
	{
		wp[++tot]=i*2-1; B[tot]=i;
	}
	dfs(tot,0,0,0,n,1);
	printf("%d\n",ans);
}

int main()
{
	init();
	doing();
	return 0;
}