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 <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN = 70;
const int MAXSLEN = 70;
const int MOD = 1000000007;

int n, slen; char s[MAXSLEN + 1];

bool used[MAXSLEN];
int mxextrablue[MAXN]; // mxextrablue[i] = maximum extra blue in segments i..numwithblue-1

int C[10 * MAXN + 1][10 * MAXN + 1];
int ways[MAXN + 1][MAXSLEN + 1][MAXSLEN + 1]; // #seg, #usedextrablue, #extrablueinlast

void inc(int &a, int b) { if ((a += b) >= MOD) a -= MOD; }
int calc(int numwithblue, int numred) {
	int havered = 0, havewithblue = 0;
	REP(i, numwithblue) mxextrablue[i] = 0;
	REP(i, slen) {
		used[i] = false;
		if (s[i] == 'r'&&havewithblue + havered < numwithblue + numred) used[i] = true, ++havered;
		if (s[i] == 'b'&&havered > 0 && havewithblue < numwithblue) used[i] = true, --havered, ++havewithblue;
		if (!used[i] && havewithblue > 0) mxextrablue[havewithblue - 1]++;
	}
	for (int i = havewithblue - 1; i > 0; --i) mxextrablue[i - 1] += mxextrablue[i];
	if (havered != numred || havewithblue != numwithblue) return 0;
	//printf("mxextrablue:"); REP(i, havewithblue) printf(" %d", mxextrablue[i]); puts("");

	int mxtotextrablue = numwithblue == 0 ? 0 : mxextrablue[0];
	REPE(i, numwithblue) REPE(j, mxtotextrablue) REPE(k, mxtotextrablue) ways[i][j][k] = 0;
	ways[0][0][0] = 1;
	REPE(i, numwithblue) REPE(usedextrablue, mxtotextrablue) REPE(lastextrablue, mxtotextrablue) if (ways[i][usedextrablue][lastextrablue] != 0) {
		//printf("\t[%d,%d,%d]=%d\n", i, usedextrablue, lastextrablue, ways[i][usedextrablue][lastextrablue]);
		int limextrablue = INT_MAX;
		FORE(di, 1, numwithblue - i) {
			int num = mxextrablue[numwithblue - i - di] - usedextrablue, den = di; if (num < 0) break;
			limextrablue = min(limextrablue, num / den); if (i != 0 && limextrablue <= lastextrablue) break;
			//printf("\t\t%d: lim=%d\n", di, limextrablue);
			FORE(extrablue, i == 0 ? 0 : lastextrablue + 1, limextrablue) {
				int cways = (ll)ways[i][usedextrablue][lastextrablue] * C[numwithblue - i][di] % MOD;
				inc(ways[i + di][usedextrablue + di*extrablue][extrablue], cways);
			}
		}
	}

	int ret = 0;
	REPE(usedextrablue, mxtotextrablue) REPE(lastextrablue, mxtotextrablue) if (ways[numwithblue][usedextrablue][lastextrablue] != 0) {
		int cways = ways[numwithblue][usedextrablue][lastextrablue];
		int nonemptywhite = numred + numwithblue > 0 ? numred + numwithblue - 1 : 1, nonemptyred = numred + usedextrablue, nonemptyblue = numwithblue + usedextrablue, canemptywhite = numred + numwithblue > 0 ? 2 : 0, canemptyred = 2 * numwithblue;
		int nonempty = nonemptywhite + nonemptyred + nonemptyblue, canempty = canemptywhite + canemptyred;
		if (nonempty > n) continue;
		int rem = n - nonempty, slots = nonempty + canempty;
		inc(ret, (ll)cways*C[rem + slots - 1][slots - 1] % MOD);
		//if (numwithblue == 2 && numred == 0) printf("[%d,%d]->%d\n", usedextrablue, lastextrablue, C[rem + slots - 1][slots - 1]);
	}
	ret = (ll)ret*C[numwithblue + numred][numred] % MOD;
	//printf("calc(%d,%d)=%d\n", numwithblue, numred, ret);
	return ret;
}

void run() {
	scanf("%d%d%s", &n, &slen, s);
	REPE(i, 10 * n) { C[i][0] = C[i][i] = 1; FOR(j, 1, i) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD; }
	int ret = 0;
	REPE(numwithblue, n) REPE(numred, n- numwithblue) ret = (ret + calc(numwithblue, numred)) % MOD;
	printf("%d\n", ret);
}

int main() {
	run();
	return 0;
}