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 rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"; return os;}
template<class T,size_t n> ostream& operator<<(ostream &os, const array<T,n> &t) {os<<"{"; rep(i,n) {os<<t[i]<<",";} os<<"}"; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const ll MOD = 1e9+7;

// n^m%MOD を求める。O( log(m) )
ll modpow(ll n, int m){
	ll ret=1;
	for(int i=1; i<=m; i<<=1, (n*=n)%=MOD){
		if( m&i ) (ret *= n) %= MOD;
	}
	return ret;
}

// 逆元を求める
ll modinv(ll n){
	return modpow( n, MOD-2 );
}

// 階乗を求める。O(1)  準備O( n*log(n) )
// fact[n]     : nの階乗
// fact.inv[n] : nの階乗の逆元
class FACTORIAL{
public:
	vector<ll> fact, inv;
	FACTORIAL(int MAX_NUM): fact(MAX_NUM), inv(MAX_NUM) {
		fact[0] = inv[0] = 1;
		for(ll i=1; i<MAX_NUM; i++){
			fact[i] = (fact[i-1] * i) % MOD;
			inv[i] = modinv( fact[i] );
		}
	}
	const ll& operator [ ] ( const int i ) const {
		return fact[i];
	}
} fact(1000006); // nの最大値を指定


// 組み合わせ(Combinationを求める) O(1)
ll cmb(unsigned int n, unsigned int r){
	if( n < r ) return 0;
	return fact[n] * fact.inv[r] % MOD * fact.inv[n-r] % MOD;
}


vector<vector<int>> vec;
void dfs(vector<int> &v, int n, int last=1){
	vec.push_back(v);
	if(last <= 1 && n >= 1){
		auto _v = v;
		_v.push_back(1);
		dfs(_v, n-2, 1);
	}
	if(last <= 2 && n >= 1){
		auto _v = v;
		_v.push_back(2);
		dfs(_v, n-2, 2);
	}
	if( last <= 2 ){
		last = 3;
	}
	for(int i = last; i <= n; i+=2){
		auto _v = v;
		_v.push_back(i);
		dfs(_v, n-i-1, i);
	}
}

int main(){
	//ios_base::sync_with_stdio(false);
	int N, K;
	string s;
	ll ans = 0;

	cin >> N >> K;
	cin >> s;

	vector<int> _v;
	dfs(_v, N);
	//cout << vec.size() << endl;

	for(auto v: vec){
		reverse(all(v));
		int a[70]={}, b[70]={}, c[70]={}, used[100]={};

		// check 1
		int pos = 0;
		if(pos < v.size()) rep(i,s.length()) if(s[i] == 'r'){
			used[i] = true;
			a[pos++] = i;
			if(pos >= v.size()) break;
		}
		if(pos < v.size()) continue;

		// check 2
		pos = 0;
		while(pos < v.size() && v[pos] < 2) pos++;
		if(pos < v.size()) rep(i,s.length()) if(s[i] == 'b' && a[pos] < i){
			used[i] = true;
			b[pos++] = i;
			while(pos < v.size() && v[pos] < 2) pos++;
			if(pos >= v.size()) break;
		}
		if(pos < v.size()) continue;

		// check 3
		pos = 0;
		while(pos < v.size() && v[pos] < 3) pos++;
		if(pos < v.size()) rep(i,s.length()) if(!used[i] && b[pos] < i){
			used[i] = true;
			c[pos]++;
			if( c[pos] >= v[pos] / 2 ){
				pos++;
				while(pos < v.size() && v[pos] < 3) pos++;
				if(pos >= v.size()) break;
			}
		}
		if(pos < v.size()) continue;

		//cout << v << "\t";
		// ok
		ll less = N;
		for(auto t: v) less -= t + 1;
		for(auto t: v) if(t == 2) less++;
		if( !v.empty() ) less++;
		//cout << "less=" << less << " ";

		ll num = v.size() + 1;  // for White
		for(auto t: v){  // for Red
			if(t == 1) num++;
			else if(t == 2) num += 2;
			else num += t / 2 + 2;
		}
		for(auto t: v){  // for Blue
			if(t == 1) ;
			else if(t == 2) num += 1;
			else num += t / 2 + 1;
		}
		//cout << "num=" << num << " ";

		ll sum = fact[v.size()];
		ll bf = -1, cnt=0;
		v.push_back(-1);
		for(auto t: v){
			cnt++;
			if(bf != t){
				//cout << "c=" << cnt << " ";
				sum = (sum * fact.inv[cnt]) % MOD;
				cnt = 0;
				bf = t;
			}
		}
		//cout << sum << " ";
		sum = (sum * cmb(num + less - 1, less)) % MOD;
		ans = (ans + sum) % MOD;
		//cout << "sum=" << sum << endl;
	}

	cout << ans << endl;

	return 0;
}