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 <algorithm>
#include <cstdio>
#define MOD 1000000007
typedef long long ll; 
inline ll quick_pow(ll a, int n)
{
	ll res = 1; 
	while (n)
	{
		if (n & 1)
			res = res * a % MOD; 
		a = a * a % MOD; 
		n >>= 1; 
	}
	return res; 
}
ll ans, fact[305], inv[305]; 
inline ll C(int n, int m)
{
	return fact[n] * inv[m] % MOD * inv[n - m] % MOD; 
}
int seq[305], n, k; 
char str[305]; 
inline void work(int len, int sum)
{
	int cur_one = 0, cur_two = 0, need = 0, arb = 0; 
	for (int i = 0; i < k; i++)
	{
		if (str[i] == 'r' && cur_one < len)
			need += seq[cur_one++] != 1; 
		else if (str[i] == 'b' && need)
		{
			need--; 
			arb += seq[cur_two++] - 2; 
		}
		else if (arb)
			arb--; 
	}
	if (cur_one < len || need || arb)
		return;
	ll res = fact[len], pos = len + 1; 
	for (int i = 0, j = 0; i < len; i = j)
	{
		while (j < len && seq[i] == seq[j])
			j++; 
		res = res * inv[j - i] % MOD; 
		pos += (j - i) * (seq[i] * 2 - 1); 
	}
	(ans += res * C(n - sum + pos - 1, pos - 1)) %= MOD; 
}
void dfs(int cur, int len, int sum)
{
	if (sum > n)
		return; 
	work(len, sum); 
	for (int i = cur; i; i--)
	{
		seq[len] = i; 
		dfs(i, len + 1, sum + std::max(1, i * 2 - 3) + (len != 0)); 
	}
}
int main()
{
	// freopen("ARC089-F.in", "r", stdin); 
	scanf("%d%d%s", &n, &k, str); 
	fact[0] = inv[0] = 1; 
	for (int i = 1; i <= 300; i++)
	{
		fact[i] = fact[i - 1] * i % MOD; 
		inv[i] = quick_pow(fact[i], MOD - 2); 
	}
	dfs(70, 0, 0); 
	printf("%lld\n", ans);
	return 0; 
}