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 <algorithm>
using namespace std;
#define N 255
#define ll long long
#define mod 1000000007
int n, k, ans, g, Ga, Gb;
int c[N][N], S[N];
char s[N];
void Calc()
{
	int ga = g, gb = g, tot = 0;
	for (int i = 1; i <= k; i++)
		if (s[i] == 'r' && ga)
			ga--;
		else
			if (s[i] == 'b' && gb > ga && S[gb] > 1)
				tot += S[gb] - 2, gb--;
			else
				if (tot)
					tot--;
	for (; S[gb] == 1;)gb--;
	if (ga || gb || tot)
		return;
	tot = 1;
	for (int i = 1, j = 0; i <= g; i = j + 1)
	{
		for (; j < g && S[j + 1] == S[i];)j++;
		tot = (ll)tot * c[j][j - i + 1] % mod;
	}
	ga = Ga - 1;
	gb = Gb + Ga;
	ans = ((ll)tot * c[n - ga + gb][gb] + ans) % mod;
}
void Find(int m, int w, int len)
{
	Calc();
	++g;
	int la = Ga, lb = Gb;
	for (int i = len; m + (i == 1 ? 2 : i * 2 - 2) <= n + 1 && w + i <= k; i++)
	{
		Ga = la + (i == 1 ? 2 : i * 2 - 2), Gb = lb + (i > 1) * 2, S[g] = i;
		Find(m + (i == 1 ? 2 : i * 2 - 2), w + i, i);
	}
	--g;
}
int main()
{
	scanf("%d%d\n%s", &n, &k, s + 1);
	for (int i = 0; i <= 250; i++)
	{
		c[i][0] = 1;
		for (int j = 1; j <= i; j++)
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
	}
	Find(0, 0, 1);
	printf("%d\n", ans);
}