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 <iostream>
#include <algorithm>
#include <vector>
using namespace std;

long long mod = 1000000007;
long long N, K;
long long nr[209][109];
long long dp[209][109], nex[209][209];

string S;
int LIM[209];
bool used[209];

void init() {
	for (int i = 0; i <= 200; i++) {
		for (int j = 0; j <= 200; j++) {
			if (i == 0 || j == 0) nr[i][j] = 1;
			else nr[i][j] = (nr[i - 1][j] + nr[i][j - 1]) % mod;
		}
	}
}

long long ncr(int n, int r) {
	if (r < 0 || n < r) return 0;
	return nr[n - r][r];
}

long long solve(int cnt1, int cnt2) {
	// ステップ 1: 前処理
	for (int i = 0; i < 200; i++) { used[i] = false; LIM[i] = 0; }

	// ステップ 2: 上限文字数の計算
	int f1 = 0, f2 = 0; vector<int> E;
	for (int i = 0; i < K; i++) {
		if (S[i] == 'r' && f1 < cnt1 + cnt2) { f1++; used[i] = true; }
		if (S[i] == 'b' && f2 < min(f1, cnt1)) { f2++; used[i] = true; E.push_back(i); }
	}
	if (f1 < cnt1 + cnt2 || f2 < cnt1) return 0;
	for (int i = 0; i < cnt1; i++) {
		for (int j = E[i] + 1; j < K; j++) {
			if (used[j] == false) LIM[i]++;
		}
	}

	// ステップ 3: 初期化
	for (int i = 0; i <= 70; i++) {
		for (int j = 0; j <= 70; j++) { dp[i][j] = 0; nex[i][j] = 0; }
	}
	
	// ステップ 4: DP の計算
	int V = N - 2 * (cnt1 + cnt2) + 1;
	int MaxLetter = (V / 2);

	dp[0][0] = 1;
	for (int i = 0; i <= MaxLetter; i++) {
		for (int j = 0; j <= cnt1; j++) {
			for (int k = 0; k <= MaxLetter; k++) {
				if (dp[j][k] == 0) continue;
				
				int cx = j, cy = k, cnt = 0;
				while (cx <= cnt1 && cy <= min(LIM[cnt1 - cx], MaxLetter)) {
					nex[cx][cy] += ncr(cx, j) * dp[j][k];
					nex[cx][cy] %= mod;
					cx += 1; cy += i;
				}
			}
		}
		for (int j = 0; j <= cnt1; j++) {
			for (int k = 0; k <= MaxLetter; k++) {
				dp[j][k] = nex[j][k];
				nex[j][k] = 0;
			}
		}
	}

	// ステップ 5: 最終的な計算
	long long ret = 0;
	for (int i = 0; i <= MaxLetter; i++) {
		int minimal_letter = 2 * (cnt1 + cnt2) - 1 + i * 2;
		int ranged = (cnt1 + cnt2 + 1) + (cnt1 * 3 + i * 2) + cnt2;
		long long V1 = dp[cnt1][i];
		long long V2 = ncr(ranged + (N - minimal_letter) - 1, N - minimal_letter);
		ret += (V1 * V2);
		ret %= mod;
	}

	long long ret2 = ncr(cnt1 + cnt2, cnt2);
	return (ret * ret2) % mod;
}

int main() {
	cin >> N >> K >> S;
	init();

	long long Answer = 0;
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= N; j++) {
			long long rem = solve(i, j);
			//cout << i << " " << j << " " << rem << endl;
			Answer += rem;
			Answer %= mod;
		}
	}

	cout << Answer << endl;
	return 0;
}