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<algorithm>
using namespace std;
char p[80];
int n, K, chk[80], Loc[36], C[36], F[150], InvF[150], Mod = 1000000007;
int D[36][36], TD[36][36]; // 한 블럭의 크기, 블럭의 개수, 쓴거의 개수

int Pow(int a, int b) {
	int r = 1;
	while (b) {
		if (b & 1)r = 1ll * r*a%Mod;
		a = 1ll * a*a%Mod; b >>= 1;
	}
	return r;
}
int Comb(int n, int r) {
	return 1ll * F[n] * InvF[r] % Mod*InvF[n - r]%Mod;
}

int Do(int A, int B) { // R* : A, RBxx : B
	int i, c1 = 0, c2 = 0, j, k, ii, jj;
	if (!A && !B)return 1;
	for (i = 0; i < K; i++) {
		chk[i] = 0;
		if (p[i] == 'r' && c1 < B) {
			chk[i] = 1;
			c1++;
		}
		if (p[i] == 'b' && c2 < c1) {
			chk[i] = 1;
			c2++;
			Loc[c2] = i;
		}
	}
	if (c1 < B || c2 < B)return 0;
	c1 = 0;
	for (i = 0; i < K; i++) {
		if (p[i] == 'r' && !chk[i] && c1 < A) {
			chk[i] = 1;
			c1++;
		}
	}
	if (c1 < A)return 0;
	for (i = 1; i <= B; i++) {
		C[B-i+1] = 0;
		for (j = Loc[i]; j < K; j++)if (!chk[j])C[B-i+1]++;
	}
	for (i = 0; i < 36; i++)for (j = 0; j < 36; j++)D[i][j] = TD[i][j] = 0;
	D[0][0] = InvF[A];

	for (i = 0; i <= n / 2; i++) {
		for (j = 0; j < 36; j++) {
			for (k = 0; k < 36; k++) {
				if (!D[j][k])continue;
				for (ii = 0;; ii++) {
					int s = (ii*i + k);
					if (ii+j > B || s * 2 + A + B + (A + B - 1) > n || C[j+ii] < s)break;
					TD[j + ii][s] = (TD[j + ii][s] + 1ll * D[j][k] * InvF[ii]) % Mod;
				}
			}
		}
		for (j = 0; j < 36; j++)for (k = 0; k < 36; k++) {
			D[j][k] = TD[j][k];
			TD[j][k] = 0;
		}
	}
	int r = 0;
	for (i = 0; i < 36; i++) {
		int c = (A + B + A + B - 1 + i * 2);
		int t = c + B * 2 + 2;
		if (!D[B][i] || n-c < 0)continue;
		r = (r + 1ll * D[B][i] * F[A+B] % Mod * Comb(t + (n - c) - 1, (n - c)))%Mod;
	}
	return r;
}
int main() {
	int i, j, res = 0;
	F[0] = 1;
	for (i = 1; i <= 142; i++)F[i] = 1ll * F[i - 1] * i%Mod;
	for (i = 0; i <= 142; i++)InvF[i] = Pow(F[i], Mod - 2);
	scanf("%d%d", &n, &K);
	scanf("%s", p);
	for (i = 0; i <= (n+1)/2; i++) {
		for (j = 0; i + j <= (n + 1) / 2; j++) {
			res = (res + Do(i, j))%Mod;
		}
	}
	printf("%d\n", res);
}