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 <queue>
#include <cstdio>
#include <cstring>

using namespace std;
const int Max_N(75);
const int Max_K(75);
const int MOD(1000000000 + 7);

constexpr int Mult(int a, int b)
{
	return a * 1LL * b % MOD;
}

constexpr int Add(int a, int b)
{
	return a + b >= MOD ? a + b - MOD : a + b;
}

void exgcd(int a, int b, int &x, int &y)
{
	if (b == 0)
		x = 1, y = 0;
	else
		exgcd(b, a % b, y, x), y -= x * (a / b);
}

inline int inverse(int a)
{
	int invx, invy;
	exgcd(a, MOD, invx, invy);
	return (invx % MOD + MOD) % MOD;
}

inline void upd(int &a, int b)
{
	a = Add(a, b);
}

int N, K, Ans, All[Max_N], Cnt[Max_N], Fac[1001], Inv[1001];
char S[Max_K];

bool check()
{
	queue<int> Q;
	int satisfy(0), need(0);
	for (int i = 1;i <= K;++i)
		if (S[i] == 'r' && satisfy < All[0])
		{
			if (All[++satisfy])
				Q.push(All[satisfy] - 1);
		}
		else
			if (S[i] == 'b' && Q.empty() == false)
				need += Q.front(), Q.pop();
			else
				need = max(0, need - 1);
	return satisfy == All[0] && Q.empty() && need == 0;
}

int F[2][Max_N];

inline int Com(int n, int m)
{
	return 0 <= m && m <= n ? Mult(Fac[n], Mult(Inv[m], Inv[n - m])) : 0;
}

int calc()
{
	memset(Cnt, 0, sizeof(Cnt));
	int Ret(Fac[All[0]]);
	for (int i = 1;i <= All[0];++i)
		++Cnt[All[i]];
	for (int i = 0;i <= N;++i)
		Ret = Mult(Ret, Inv[Cnt[i]]);
	int can_0(2), other(0);
	for (int i = 1;i <= All[0];++i)
	{
		if (i + 1 <= All[0])
			++other;
		if (All[i] == 0)
			++other;
		else
			can_0 += 2, other += (All[i] - 1) + All[i];
	}
	return Mult(Ret, Com(N + can_0 - 1, can_0 + other - 1));
}

void dfs(int last, int less)
{
	if (All[0])
		if (check())
			upd(Ans, calc());
		else
			return;
	for (int n = last, _less;n >= 0;--n)
	{
		if ((_less = less + (n == 0 ? 1 : n + (n - 1)) + (All[0] != 0)) > N)
			continue;
		All[++All[0]] = n, dfs(n, _less), --All[0];
	}
}

int main()
{
	Fac[0] = 1;
	for (int i = 1;i <= 1000;++i)
		Fac[i] = Mult(Fac[i - 1], i);
	Inv[1000] = inverse(Fac[1000]);
	for (int i = 1000 - 1;i >= 0;--i)
		Inv[i] = Mult(Inv[i + 1], i + 1);
	scanf("%d%d", &N, &K);
	scanf("%s", S + 1);
	Ans = 1, dfs(N, 0), printf("%d", Ans);
	return 0;
}