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 <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cerr << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; }
template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

const ll MOD = TEN(9) + 7;
const int MX = 200;
ll inv[MX], fact[MX], ifact[MX];

void init() {
    inv[1] = 1;
    for (int i = 2; i < MX; ++i) {
        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
    }
    fact[0] = ifact[0] = 1;
    for (int i = 1; i < MX; ++i) {
        fact[i] = fact[i-1] * i % MOD;
        ifact[i] = ifact[i-1] * inv[i] % MOD;
    }
}

ll comb(int n, int r) {
    if (n < 0 || r < 0 || r > n) return 0;
    return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
}

int N, K;
string s;
ll ans;

int cnt = 0;
void calc(V<int>& vec) { //based on blue
	if (vec.empty()) {
		ans = (ans + 1) % MOD;
		return ;
	}

	int sz = vec.size();

	V<int> us(K);
	V<int> piv(sz);

	int now = 0;
	for (int i = sz - 1; i >= 0; --i) {
		int x = vec[i];
		while (now < K && s[now] == 'b') {
			++now;
		}
		if (now < K) {
			piv[i] = now;
			us[now] = 1;
			now++;
		} else {
			return ;
		}
	}

	now = 0;

	for (int i = sz - 1; i >= 0; --i) {
		int x = vec[i];
		if (x >= 2) {
			chmax(now, piv[i] + 1);
			while (now < K && s[now] == 'r') {
				++now;
			}
			if (now < K) {
				piv[i] = now;
				us[now] = 1;
				now++;
			} else {
				return ;
			}
		}
	}

	now = 0;

	for (int i = sz - 1; i >= 0; --i) {
		int x = vec[i];
		if (x >= 3) {
			x -= 2;
			chmax(now, piv[i] + 1);
			rep(t, x) {
				while (now < K && us[now]) {
					++now;
				}
				if (now < K) {
					us[now] = 1;
					now++;
				} else {
					return ;
				}
			}
		}
	}

	int need = sz - 1;
	int bs = 0;

	for (int x : vec) {
		if (x == 1) {
			++need;
		} else {
			++bs;
			need += x * 2 - 3;
		}
	}

	if (need > N) {
		return ;
	}

	ll coef = fact[sz];
	{

		rep(i, sz) {
			if (i == 0 || vec[i] != vec[i-1]) {
				int c = 0;
				for (int j = i; j < sz; ++j) {
					if (vec[j] == vec[i]) {
						++c;
					} else {
						break;
					}
				}
				coef = coef * ifact[c] % MOD;
			}
		}
	}

	//dump(vec);
	//dump(need);

	coef = coef * comb(N - need + (need + 1 + bs * 2), need + 1 + bs * 2);

	ans = (ans + coef) % MOD;
	++cnt;
}

void gen(int p, int s, V<int>& vec) {
	bool en = (s + ((p == 1) ? 1 : p * 2 - 3) + vec.size() > N);
	if (p == K + 1 || en) {
		calc(vec);
		return ;
	}

	gen(p + 1, s, vec);

	for (; ; ) {
		if (p == 1) {
			++s;
		} else {
			s += p * 2 - 3;
		}
		if (s + vec.size() > N) {
			break;
		}
		vec.pb(p);		
		gen(p + 1, s, vec);
	}
	while (vec.size() && vec.back() == p) {
		vec.pop_back();
	}
}

int main() {
	init();

	cin >> N >> K >> s;
	{
		V<int> vec;
		gen(1, 0, vec);
	}
	//dump(cnt);

	cout << ans << endl;

	return 0;
}