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

#define rep(i, x, n) for(int i=x;i<=n;i++)
#define pr make_pair
#define fi first
#define se second

const int MOD = int(1E9) + 7;
const int MAX = 420000;
const int HASHSIZE = 1000037;

inline int add(int x, int y) {x += y; return x >= MOD ? x - MOD : x;}
inline int sub(int x, int y) {x -= y; return x < 0 ? x + MOD : x;}
inline int mul(int x, int y) {return (int) (1LL * x * y % MOD);}
int mpow(int b, int p) {
	int r; for(r=1;p;p>>=1,b=mul(b,b))
		if( p & 1 ) r = mul(r, b);
	return r;
}

struct node{
	int x[40], cnt;
	int get() {
		int h = 0;
		for(int i=0;i<cnt;i++)
			h = (131LL*h + x[i]) % HASHSIZE;
		return h;
	}
	void print() {
		for(int i=0;i<cnt;i++)
			printf("%d%c", x[i], i + 1 == cnt ? '\n' : ' ');
	}
	bool equal(const node &b) {
		if( cnt != b.cnt ) return false;
		for(int i=0;i<cnt;i++)
			if( x[i] != b.x[i] ) return false;
		return true;
	}
}st[MAX + 5];
vector<pair<node, int> >h[HASHSIZE];
void insert(node a, int i) {h[a.get()].push_back(pr(a, i));}
int search(node a) {
	int x = a.get();
	for(unsigned i=0;i<h[x].size();i++)
		if( a.equal(h[x][i].fi) ) return h[x][i].se;
	return -1;
}

int l[75], tot, N, K;
void dfs(int s, node a, int x) {
	tot++, insert(st[tot] = a, tot);
	for(int i=x;i<=N&&l[i]<=s;i++)
		a.x[a.cnt++] = i, dfs(s - l[i], a, i), a.x[--a.cnt] = i;
}

int f[MAX + 5], fct[505], ifct[505], c[505][505];
void init() {
	rep(i, 0, 500) rep(j, 0, i)
		c[i][j] = (j == 0 ? 1 : add(c[i - 1][j], c[i - 1][j - 1]));
	fct[0] = 1; rep(i, 1, 500) fct[i] = mul(fct[i - 1], i);
	ifct[500] = mpow(fct[500], MOD - 2);
	for(int i=499;i>=0;i--) ifct[i] = mul(ifct[i + 1], i + 1);
	
	l[1] = 2; rep(i, 2, N) l[i] = (i - 1) << 1; dfs(N, (node){}, 1);
	rep(i, 1, tot) {
		int a = 1, b = 0, t = 1, p = 1;
		rep(j, 1, st[i].cnt - 1) {
			if( st[i].x[j] != st[i].x[j-1] )
				t = mul(t, ifct[p]), p = 1;
			else p++;
		}
		t = mul(t, ifct[p]);
		rep(j, 0, st[i].cnt - 1) {
			b += l[st[i].x[j]];
			if( st[i].x[j] != 1 ) a += 2;
		}
		f[i] = mul(mul(fct[st[i].cnt], t), c[N + a - 1][a + b - 1]);
	}
//	printf("%d\n", tot);
}

int tg[75], q[75]; char s[75];
int main() {
	scanf("%d%d%s", &N, &K, s + 1), N++, init();
	
	int ans = 0;
	rep(i, 1, tot) {
		int cnt1 = 0, pos = -1;
		rep(j, 0, st[i].cnt - 1) {
			if( st[i].x[j] != 1 ) {
				pos = j;
				break;
			} else cnt1++;
		}
		
		int hd = 1, tl = 0, p = st[i].cnt - cnt1;
		rep(j, 1, K) tg[j] = -1;
		for(int j=1;p&&j<=K;j++) {
			if( s[j] == 'r' ) q[++tl] = j;
			else if( hd <= tl ) tg[q[hd++]] = 0, tg[j] = 1, p--;
		}
		
		int cnt[2] = {}; bool flag = true;
		for(int j=K;j>=1;j--) {
			if( tg[j] == -1 ) cnt[s[j] == 'r' ? 0 : 1]++;
			else if( tg[j] == 1 ) {
				int tmp = st[i].x[pos] - 2;
				while( cnt[1] && tmp ) cnt[1]--, tmp--;
				while( cnt[0] && tmp ) cnt[0]--, tmp--;
				if( tmp ) {
					flag = false;
					break;
				}
				pos++;
			}
		}
		
		if( flag && cnt[0] >= cnt1 && p == 0 ) ans = add(ans, f[i]);
	}
	printf("%d\n", ans);
}