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:
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

template<ll MOD, int REV = 1>
class ModInt {
	public:
	static bool flag[REV];
	static ll rev[REV];
	static ll pw(ll a, ll b) {
		ll ans = 1; while (b) {
			while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
			ans = (ans * a) % MOD, --b;
		} return ans;
	}
	ll x;
	ModInt(): x(0) {}
	ModInt(ll x): x(x % MOD) {}
	ModInt operator+(ModInt b) {
		ModInt ans;
		ans.x = x + b.x;
		if (ans.x >= MOD)
			ans.x -= MOD;
		return ans;
	}
	ModInt &operator+=(ModInt b) {
		x += b.x;
		if (x >= MOD)
			x -= MOD;
		return *this;
	}
	ModInt operator-(ModInt b) {
		ModInt ans;
		ans.x = x - b.x;
		if (ans.x < 0)
			ans.x += MOD;
		return ans;
	}
	ModInt &operator-=(ModInt b) {
		x -= b.x;
		if (x < 0)
			x += MOD;
		return *this;
	}
	ModInt operator-() {
		ModInt ans;
		if (x == 0)
			return ans;
		ans.x = MOD - x;
		return ans;
	}
	ModInt operator*(ModInt b) {
		return ModInt(x * b.x);
	}
	ModInt &operator*=(ModInt b) {
		x = (x * b.x) % MOD;
		return *this;
	}
	ModInt inv() {
		if (MOD >= 2) {
			if (x >= REV)
				return ModInt(pw(x, MOD - 2));
			else {
				if (flag[x])
					return rev[x];
				else {
					flag[x] = 1;
					return rev[x] = pw(x, MOD - 2);
				}
			}
		}
		return ModInt();
	}
	ModInt operator/(ModInt b) {
		return ModInt(x * b.inv().x);
	}
	ModInt& operator/=(ModInt b) {
		x = (x * b.inv().x) % MOD;
		return *this;
	}
	bool operator==(ModInt b) {
		return x == b.x;
	}
	bool operator!=(ModInt b) {
		return x != b.x;
	}
};

template<ll MOD, int REV>
bool ModInt<MOD, REV>::flag[] = {};

template<ll MOD, int REV>
ll ModInt<MOD, REV>::rev[] = {};

const ll MOD = 1e9 + 7;

using num = ModInt<MOD, 100>;

num ans = 0;
const int MX = 72;

num dp[MX][MX];

string s;

struct st {
	int pos;
	int fr;
	int nd;
	deque<int> dq;
	st() {
		pos = fr = nd = 0;
	}
	int add(int sz) {
		while (pos < s.size() && s[pos] == 'b') {
			if (nd) {
				--nd;
				fr += dq.front();
				dq.pop_front();
			}
			else if (fr)
				--fr;
			++pos;
		}
		if (pos == s.size())
			return 0;
		pos += 1;
		if (sz) {
			++nd;
			dq.push_back(sz - 1);
		}
		return 1;
	}
	int check() {
		int pos2 = pos;
		int fr2 = fr;
		int nd2 = nd;
		auto dq2 = dq;
		while (pos2 < s.size()) {
			if (s[pos2] == 'r') {
				if (fr2)
					--fr2;
			}
			else {
				if (nd2) {
					--nd2;
					fr2 += dq2.front();
					dq2.pop_front();
				}
				else if (fr2)
					--fr2;
			}
			++pos2;
		}
		if (nd2 || fr2)
			return 0;
		return 1;
	}
};

int gn;

double sum = 0;


int Cnt;
vector<int> stck;

void run(int n, int cnt, int lst, int cntlst, st cur, array<num, MX> a) {
	if (cur.check()) {
		for (int i = 0; i <= gn; ++i)
			ans += a[i];
	}
	else
		return;

	if (n >= 2) {
		for (int i = min(lst, n / 2); i >= 0; --i) {
			auto cur2 = cur;
			if (!cur2.add(i))
				continue;
			if (lst == i)
				++cntlst;
			else
				cntlst = 1;
			array<num, MX> b = {};
			//auto start = std::chrono::high_resolution_clock::now();
			for (int j = 0; j <= gn; ++j) {
				if (a[j].x == 0)
					continue;
				for (int k = 2 * i; j + k <= gn; ++k)
					b[j + k] += a[j] * dp[i][k];
			}
			for (int j = 0; j <= gn; ++j) {
				b[j] *= (cnt + 1);
				if (cntlst != 1)
					b[j] /= cntlst;
			}
			//auto end = std::chrono::high_resolution_clock::now();
			//sum += std::chrono::duration<ld>(end - start).count();
			stck.push_back(i);
			if (i != 0)
				run(n - 2 * i, cnt + 1, i, cntlst, cur2, b);
			else
				run(n - 2, cnt + 1, i, cntlst, cur2, b);
			stck.pop_back();
		}
	}
}


num fc[MX * 2];
num bfc[MX * 2];

num cnk(int n, int k) {
	if (k > n)
		return 0;
	return fc[n] * bfc[k] * bfc[n - k];
}

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	cout.setf(ios::fixed), cout.precision(20);
	fc[0] = 1;
	for (int i = 1; i < 2 * MX; ++i)
		fc[i] = (fc[i - 1] * i);
	for (int i = 0; i < 2 * MX; ++i)
		bfc[i] = fc[i].inv();
	int n, k;
	cin >> n >> k;
	cin >> s;
	n += 1;
	gn = n;
	for (int i = 2; i < MX; ++i)
		dp[0][i] = i - 1;
	for (int i = 1; i < MX; ++i) {
		for (int j = i * 2; j < MX; ++j) {
			dp[i][j] = cnk(j - 2 * i + 2 * i + 1, 2 * i + 1);
		}
	}
	run(n, 0, n, 0, {}, {1});
	cout << ans.x << "\n";
	//cerr << sum << "\n";
	return 0;
}