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 int long long

int n,k;
int C[555][555];
int inv[555];
char seq[75];
int mat[75],fact[555];
int pos[75],cnt;
int ln[75];
int ans;
const int mod = 1000000007;

int qpow(int base,int tms)
{
	int tmp = 1;
	while(tms)
	{
		if(tms & 1) tmp = tmp * 1ll * base % mod;
		base = base * 1ll * base % mod;
		tms >>= 1;
	}
	return tmp;
}

bool chk(int cn)
{
	if(cn > cnt) return false;
	static int sum[75]; memset(sum,0,sizeof(sum));
	for(int i = cn;i >= 1; -- i)
	{
		if(!pos[i]) return false;
		sum[pos[i]] ++;
		if(ln[cn - i + 1] >= 2)
		{
			if(!mat[pos[i]]) return false;
			sum[mat[pos[i]]] += ln[cn - i + 1] - 1;
		}
	}
	for(int i = k;i >= 1; -- i)
	{
		sum[i] += sum[i + 1];
		if(sum[i] > k - i + 1) return false;
	}
	return true;
}

bool dfs(int mi,int cnt,int mus)
{
	if(!chk(cnt)) return false;
	int k = cnt + 1;
	for(int i = 1;i <= cnt; ++ i)
		k += 2 * ln[i] - 1;
	int as = C[n - mus + k - 1][k - 1];
	if(k > 500) cerr << k << endl; 
	int p = 0;
	for(int i = 1;i <= cnt; ++ i)
	{
		if(ln[i] != ln[i - 1])
			as = as * 1ll * inv[p] % mod,p = 0;
		p ++;
	}
	as = as * 1ll * inv[p] % mod;
	as = as * 1ll * fact[cnt] % mod;
	ans = (ans + as) % mod; 
	for(int i = mi;i <= 70; ++ i)
	{
		ln[cnt + 1] = i;
		int nw = mus;
		if(cnt) nw ++;
		nw += i <= 2 ? 1 : 2 * i - 3;
		if(nw > n) break;
		if(!dfs(i,cnt + 1,nw)) break;
	}
	return true;
}

signed main()
{
	scanf("%lld%lld",&n,&k);
	scanf("%s",seq + 1);
	int po = 1;
	for(int i = 1;i <= k; ++ i)
	{
		if(seq[i] == 'r')
		{
			po = max(po,i);
			while(po <= k && seq[po] != 'b') po ++;
			if(po <= k)
				mat[i] = po ++;
			pos[++ cnt] = i;
		}
	}
	C[0][0] = 1;
	fact[0] = 1;
	inv[0] = 1;
	int pre = 1;
	for(int i = 1;i <= 550; ++ i)
	{
		pre = pre * 1ll * i % mod;
		fact[i] = pre;
		inv[i] = qpow(pre,mod - 2);
		C[i][0] = 1;
		for(int j = 1;j <= i; ++ j)
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
	}
	dfs(1,0,0);
	printf("%lld\n",ans);
	return 0;
}