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:
// Tenshi ni Fureta yo!

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned int UI;
typedef pair<int, int> pii;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define MP make_pair
#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

inline void proc_status()
{
	ifstream t("/proc/self/status");
	cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}

template<typename T> inline int chkmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline int chkmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template<typename T> inline T sqr(const T &val) { return val * val; }

namespace fastIO
{
	const int MAX_BUFFER_SIZE = 1 << 16;

	char buffer[MAX_BUFFER_SIZE], *cur = buffer, *ed = buffer;

	inline char getc() { return *(cur == ed ? ed = buffer + fread(buffer, 1, MAX_BUFFER_SIZE, stdin), cur = buffer : cur)++; }
}
using fastIO::getc;

template<typename T> inline T read()
{
	register T sum(0), fg(1);
	register char ch(getc());
	for(; !isdigit(ch); ch = getc()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getc()) sum = sum * 10 - '0' + ch;
	return sum * fg;
}

// END tpl.

inline char safe_getc()
{
	register char ch(getc());
	while(!isgraph(ch)) ch = getc();
	return ch;
}

const int MOD = (int) 1e9 + 7;

inline int fpm(int x, int y)
{
	int res = 1;
	for(; y; y >>= 1, x = (LL) x * x % MOD) if(y & 1) res = (LL) res * x % MOD;
	return res;
}

inline int inv(int x) { assert(x); return fpm(x, MOD - 2); }

namespace MATH
{
	const int n = (int) 1e5;

	int fac[n + 5], ifac[n + 5];

	inline void init()
	{
		fac[0] = 1;
		for(int i = 1; i <= n; ++i) fac[i] = (LL) fac[i - 1] * i % MOD;
		ifac[n] = inv(fac[n]);
		for(int i = n - 1; i >= 0; --i) ifac[i] = (LL) ifac[i + 1] * (i + 1) % MOD;
	}

	inline int C(int N, int M) { return N < 0 || M < 0 || N < M ? 0 : (LL) fac[N] * ifac[N - M] % MOD * ifac[M] % MOD; }
}
using MATH::fac;
using MATH::ifac;
using MATH::C;

const int MAXN = 70;

int n, K;

char s[MAXN + 5];

inline void input()
{
	n = read<int>(), K = read<int>();
	for(int i = 1; i <= K; ++i) s[i] = safe_getc();
}

int a[MAXN + 5];

inline int check(int N)
{
	static int pos[MAXN + 5], vis[MAXN + 5];
	memset(vis, 0, sizeof vis);

	int lstr = 0;
	for(int i = 1; i <= N; ++i)
	{
		pos[i] = K + 1;
		for(int j = lstr + 1; j <= K; ++j) if(s[j] == 'r' && !vis[j]) { vis[lstr = pos[i] = j] = 1; break; }
		if(pos[i] == K + 1) return 0;

		if(a[i] > 1)
		{
			for(; pos[i] <= K; ++pos[i]) if(!vis[pos[i]] && s[pos[i]] == 'b') { vis[pos[i]] = 1; break; }
			if(pos[i] == K + 1) return 0;
		}
	}

	for(int i = 1; i <= N; ++i) if(a[i] > 2)
	{
		int cnt = 2;
		for(int j = pos[i] + 1; cnt < a[i] && j <= K; ++j) if(!vis[j]) vis[j] = 1, ++cnt;
		if(cnt < a[i]) return 0;
	}

	return 1;
}

inline int div_into(int N, int M) { return C(N + M - 1, M - 1); }

inline int calc(int N, int S)
{
	int res = fac[N], M = N + 1;
	for(int i = 1, j; i <= N; i = j)
	{
		for(j = i; j <= N && a[j] == a[i]; ++j);
		res = (LL) res * ifac[j - i] % MOD;
		M += (a[i] * 2 - 1) * (j - i);
	}
	return (LL) res * div_into(n - S, M) % MOD;
}

int ans = 0;

inline void dfs(int k, int lst, int S)
{
	if(S > n) return;
	if(check(k)) (ans += calc(k, S)) %= MOD;

	for(int i = 1; i <= lst; ++i) a[k + 1] = i, dfs(k + 1, i, S + (i == 1 ? 1 : i * 2 - 3) + (k > 0));
}

inline void solve()
{
	ans = 0, dfs(0, K, 0);
	printf("%d\n", (ans + MOD) % MOD);
}

int main()
{
#ifdef K_ON
	freopen("F.in", "r", stdin);
	freopen("F.out", "w", stdout);
#endif

	MATH::init();
	input();
	solve();

	return 0;
}