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 <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define inver(a) power(a,mod-2)
using namespace std;
template<class T> inline bool Cmax(T &x,T y) {return x<y?x=y,1:0;}
typedef long long ll;
const int mod=1e9+7;
const int maxn=1000+5;
const int maxk=70+5;
int n,k;
int an;
int r[maxk],b[maxk];
int fac[maxn];
int inv[maxn];
int num[maxk];
bool vis[maxk];
char s[maxk];
vector<int> a; 
inline int add(int x) {return x>=mod?x-mod:x;}
ll power(ll x,ll y)
{
	ll re=1;
	while(y)
	{
		if(y&1) re=re*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return re;
}
inline int binom(int x,int y)
{
	return (ll)fac[x]*inv[y]%mod*inv[x-y]%mod;
}
bool check()
{
	memset(vis,0,sizeof(vis));
	for(int i=0,j=1;i<a.size();++i)
	{
		while(j<=k&&s[j]!='r') ++j; if(j>k) return 0;
		r[i]=j,vis[j++]=1;
	}
	for(int i=0,j=1;i<a.size();++i) if(a[i]>=2)
	{
		Cmax(j,r[i]+1);
		while(j<=k&&s[j]!='b') ++j; if(j>k) return 0;
		b[i]=j,vis[j++]=1;
	}
	for(int i=0,j=1;i<a.size();++i) if(a[i]>=3)
	{
		Cmax(j,b[i]+1);
		int T=a[i]-2; while(T--)
		{
			while(j<=k&&vis[j]) ++j; if(j>k) return 0;
			vis[j++]=1;
		}
	}
	return 1;
}
void dfs(int rest,int las)
{
	if(check())
	{
		int v=a.size()+1;
		for(int i=0;i<a.size();++i)
		{
			v+=num[a[i]];
			if(a[i]>1) v+=2;
		}
		int re=(ll)binom(rest+v-1,rest)*fac[a.size()]%mod;
		for(int i=0,j;i<a.size();i=j)
		{
			j=i; while(j<a.size()&&a[j]==a[i]) ++j;
			re=(ll)re*inv[j-i]%mod;
		}
		an=add(an+re);
	}
	for(int i=1;i<=las;++i)
	{
		if(num[i]+1>rest) break;
		a.push_back(i);
		dfs(rest-num[i]-1,i);
		a.pop_back();
	}
}
void init(int n)
{
	fac[0]=1;
	for(int i=1;i<=n;++i)
	{
		fac[i]=(ll)fac[i-1]*i%mod;
	}
	inv[n]=inver(fac[n]);
	for(int i=n;i>=1;--i)
	{
		inv[i-1]=(ll)inv[i]*i%mod;
	}
}
int sol()
{
	init(1000);
	an=1;
	num[1]=1;
	num[2]=1;
	for(int i=3;i<=70;++i) num[i]=num[i-1]+2;
	for(int i=1;;++i)
	{
		if(num[i]>n) break;
		a.push_back(i);
		dfs(n-num[i],i);
		a.pop_back();
	}
	return an;
}
int main()
{
	scanf("%d%d",&n,&k);
	scanf("%s",s+1);
	printf("%d\n",sol());
	return 0;
}