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 meow(args...) fprintf(stderr, args)
typedef unsigned u32;
typedef long long s64;
typedef unsigned long long u64;
template<class T1, class T2> inline bool cmin(T1 &a, const T2 &b) {return b<a?(a=b, true):false;}
template<class T1, class T2> inline bool cmax(T1 &a, const T2 &b) {return a<b?(a=b, true):false;}
const u32 P=1e9+7;
inline u32 &inc(u32 &a, u32 b) {return (a+=b)<P?a:(a-=P);}
inline u32 &dec(u32 &a, u32 b) {return (a-=b)&0x80000000?(a+=P):a;}
inline u32 sum(u32 a, u32 b) {return (a+=b)<P?a:a-P;}
inline u32 dif(u32 a, u32 b) {return (a-=b)&0x80000000?a+P:a;}
u64 power(u64 a, int b) {
	u64 ans=1;
	for(; b; a=a*a%P, b/=2) if(b&1) ans=ans*a%P;
	return ans;
}

int n, k, rcnt, f[70];
u32 ans, c[500][500], fac[500], inv[500];
char s[71];
void search(int len, int last, int sum) {
	if(len>rcnt) return;
	int r=0, nz=0, b=0, a=0;
	while(nz<len&&f[nz]==0) ++nz;
	nz=len-nz;
	for(int i=0; i<k&&(b!=nz||a!=0); ++i) {
		if(s[i]=='r') if(r<len) ++r; else if(a) --a;
		if(s[i]=='b') if(b<r&&b<nz) ++b, a+=f[len-b]-1; else if(a) --a;
	}
	if(b==nz&&a==0) {
		int fsum=len;
		u64 q=fac[len];
		for(int i=0, j; i<len; ++i) {
			fsum+=f[i];
			if(i==0||f[i]!=f[i-1]) j=0;
			q=q*inv[++j]%P;
		}
		ans=(ans+q*c[n+1+2*nz][2*fsum])%P;
		if(sum) {
			int &F=f[len];
			for(F=last; F<=sum; ++F) search(len+1, F, sum-(F?F:1));
		}
	}
}
int main() {
	for(int i=0; i<500; ++i) {
		c[i][0]=c[i][i]=1;
		for(int j=1; j<i; ++j) c[i][j]=sum(c[i-1][j-1], c[i-1][j]);
	}
	fac[0]=1;
	for(int i=1; i<500; ++i) fac[i]=(u64)fac[i-1]*i%P;
	inv[1]=1;
	for(int i=2; i<500; ++i) inv[i]=(u64)(P-P/i)*inv[P%i]%P;
	assert(scanf("%d%d%s", &n, &k, s)==3);
	rcnt=std::count(s, s+k, 'r');
	search(0, 0, (n+1)/2);
	printf("%u\n", ans);
	return 0;
}