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 <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

const int MX = 605;
const int MM = 1000000007;

int C[MX][MX];
ll I[MX], FI[MX], F[MX];
int A[MX], sz = 0;
string S;
ll ans = 1;
int N, K;
int pr[75] = {};

int sum = -1, t = 2;

void update()
{
	if( N < sum ) return;
	int cnt = 0, red = 0, blue = 0;
	for(char c : S){
		if( c == 'r' ){
			if( red < sz) red++;
			else cnt -= cnt>0;
		}
		else{
			if( blue < red && A[blue] >= 2 ) cnt += A[blue++]-2;
			else cnt -= cnt>0;
		}
	}
	if(cnt || red != sz || A[blue] >= 2) return;

	ll m = F[sz];
	for(int i = 0; i < sz; i++) pr[A[i]] += 1;
	for(int i = 0; i <= A[0]; i++){
		if(pr[i]) m = m * FI[pr[i]] % MM;
		pr[i] = 0;
	}

	ans = (ans + C[t+N-1][N-sum] * m) % MM;
}

void dfs(int K, int mx){
	if( K == 0 ) return;
	for(int i = mx; i >= 1; i--){
		A[sz++] = i;
		t += i >= 2 ? 2 : 0;
		sum += i == 1 ? 2 : i*2-2;

		update();
		dfs(K-i, min(i, K-i));

		A[--sz] = 0;
		t -= i >= 2 ? 2 : 0;
		sum -= i == 1 ? 2 : i*2-2;
	}
}

int main()
{
	F[0] = FI[0] = 1;
	I[1] = 1;
	for(int i = 2; i < MX; i++) I[i] = (MM-I[MM%i]) * (MM/i) % MM;
	for(int i = 1; i < MX; i++) F[i] = F[i-1] * i % MM;
	for(int i = 1; i < MX; i++) FI[i] = FI[i-1] * I[i] % MM;
	scanf("%d%d", &N, &K);
	for(int i = 0; i < MX; i++){
		C[i][0] = 1;
		for(int j = 1; j <= i; j++) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MM;
	}
	cin >> S;
	dfs(K, K);
	printf("%lld\n", ans);
}