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<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

namespace Shi_Jian_Shi_Jian_Yan_Zhen_Li_De_Wei_Yi_Biao_Zhun____________________By_a_Believer
{
	typedef long long ll;
	const int N=72,M=2333,MOD=1000000007;
	inline void inc(int a,int &b){b=(a+b)%MOD;}
	inline ll inv(int x){return x==1?1:(-(MOD/x)*inv(MOD%x)%MOD);}

	int fact[M];
	int C[M][M];

	void initialize()
	{
		for(int i=0;i<M;i++)C[i][0]=1;
		for(int i=1;i<M;i++)
			for(int j=1;j<M;j++)
				C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
		fact[0]=1;
		for(int i=1;i<M;i++)fact[i]=(ll)fact[i-1]*i%MOD;
	}

	char s[N];
	int n,m,ans;

#define ml(x) (std::max(1,((x)-1)*2-1))

	int f[N];

	bool check(int tot)
	{
		int cnt=0,ind=tot,dni=tot;

		for(int i=1;i<=m;i++)
			if(s[i]=='r')
			{
				if(ind)ind--;
				else cnt-=cnt>0;
			}
			else
			{
				if(dni && dni>ind && f[dni]>1)
				{
					cnt+=f[dni]-2;
					dni--;
				}
				else cnt-=cnt>0;
			}
		return !ind && (!dni || f[dni]==1) && !cnt;
	}

	int calc(int tot)
	{
		int ret=fact[tot],tmp=0,cnt=0,fk=0;
		for(int i=1;i<=tot;i++)
		{
			cnt+=ml(f[i]),fk+=f[i]*2-1;
			tmp++;
			if(i==tot || f[i]!=f[i+1])
				ret=(ll)ret*inv(fact[tmp])%MOD,tmp=0;
		}
		cnt+=tot?tot-1:0,fk+=tot+1;
		
		ret=((ll)ret*C[n-cnt+fk-1][fk-1]%MOD+MOD)%MOD;

//		printf("cnt = %d , fk = %d\n",n-cnt,fk);
//		printf("ret = %d\n",ret);

		return ret;
	}

	void dfs(int p=0,int x=1,int len=n)
	{
		
		if(check(p))inc(calc(p),ans);

		int &y=f[p+1];
		for(y=x;ml(y)<=len;y++)
			dfs(p+1,y,std::max(len-ml(y)-1,0));
	}

	void solve()
	{
		initialize();
		scanf("%d%d",&n,&m);
		scanf("%s",s+1);
		ans=0,dfs();
		printf("%d\n",ans);
	}
}

int main()
{
	Shi_Jian_Shi_Jian_Yan_Zhen_Li_De_Wei_Yi_Biao_Zhun____________________By_a_Believer::solve();
	return 0;
}