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>
#define For(i,l,r) for(int i = (l),i##end = (r);i <= i##end;i++)
#define Fordown(i,r,l) for(int i = (r),i##end = (l);i >= i##end;i--)
#define debug(x) cout << #x << " = " << x << endl

using namespace std;

typedef long long ll;

template <typename T> inline bool chkmin(T &x,T y) { return y < x ? x = y,1 : 0; }
template <typename T> inline bool chkmax(T &x,T y) { return x < y ? x = y,1 : 0; }

const int INF = 0x3f3f3f3f;
const int N = 70 + 10,mod = 1e9 + 7;

int a[N],vis[N],fac[N << 1],inv[N << 1],Pos[N];
char str[N];

int n,k,ans = 0;

inline int read() {
	int x = 0,flag = 1;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-')ch = getchar();
	if(ch == '-')flag = -1,ch = getchar();
	while(isdigit(ch))x = (x << 3) + (x << 1) + (ch - '0'),ch = getchar();
	return x * flag;
}

inline int fpm(int A,int b) {
	int res = 1;
	while(b) {
		if(b & 1) res = 1ll * res * A % mod;
		A = 1ll * A * A % mod,b /= 2;
	}
	return res;
}

inline int C(int A,int B) {
	return 1ll * fac[A] * inv[B] % mod * inv[A - B] % mod;
}

inline void Calc(int len,int sum) {
	memset(vis,0,sizeof(vis)),memset(Pos,0,sizeof(Pos));
	int lasr = 0,lasb = 0;
	For(i,1,len) {
		int pos = 0;
		For(j,lasr + 1,k) if(!vis[j] && str[j] == 'r') {
			vis[j] = true;
			pos = lasr = j;break;
		}
		if(!pos) return;
		if(a[i] < 2) continue;
		For(j,max(pos,lasb) + 1,k) if(!vis[j] && str[j] == 'b') {
			vis[j] = true;
			Pos[i] = lasb = j;break;
		}
		if(!Pos[i]) return;
	}
	int Las = 0;
	For(i,1,len) {
		if(a[i] < 3) continue;
		int cnt = 0;
		For(j,max(Pos[i],Las) + 1,k) {
			if(!vis[j]) cnt++,vis[j] = true;
			Las = j;
			if(cnt == a[i] - 2) break;
		}
		if(cnt < a[i] - 2) return;
	}
	int Inv = fac[len],tot = len + 1;
	for(int i = 1,j = 1;i <= len;i = j + 1) {
		for(j = i;j < len && a[j + 1] == a[i];j++);
		Inv = 1ll * Inv * inv[j - i + 1] % mod;
		tot += (j - i + 1) * (a[i] * 2 - 1);
	}
	ans = (ans + 1ll * Inv * C(n - sum + tot - 1,tot - 1)) % mod;
}

inline void dfs(int res,int Mn,int cur) {
	if(res < 0) return;
	Calc(cur - 1,n - res);
	if(res == 0) return;
	For(i,1,min(res + 1,Mn)) a[cur] = i,dfs(res - (i == 1 ? 1 : i * 2 - 3) - (cur > 1),i,cur + 1);
}

inline void init(int Lim) {
	fac[0] = 1;
	For(i,1,Lim) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[Lim] = fpm(fac[Lim],mod - 2);
	Fordown(i,Lim,1) inv[i - 1] = 1ll * inv[i] * i % mod;
}

int main() {

	n = read(),k = read();
	init(150);
	scanf("%s",str + 1);

	dfs(n,70,1);

	printf("%d\n",ans);

	return 0;
}