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>
using namespace std;
typedef long long ll;
const int N = 600;
const int MOD = 1e9 + 7;
 
int n, k, tot = 0, _left, a[N]; 
ll ans = 0, c[N][N]; 

inline ll add( ll a, ll b ) { ll ret = a + b; if( ret > MOD ) ret -= MOD; return ret; }

inline void init_c( int size ) 
{
	for( int i = 0; i <= size; i ++ )
	{
		c[i][0] = 1;
		for( int j = 1; j <= i; j ++ )
			c[i][j] = add( c[i-1][j], c[i-1][j-1] );
//		printf( "C(5, 3) = %lld\n", c[5][3] );
	}
} 

string opt;

inline bool check()
{
	if( !tot ) return false;
	
	int now1 = 1, now2 = 1, c = 0;
	// now1: 红色生成到的段
	// now2: 蓝色生成到的段 
	// c: 剩余需要的 划分成段的 数量 
	
	for( int i = 1; i <= k; i ++ )
	{
		if( now1 > tot && a[now2] <= 1 && !c ) return true;
		// 优先生成新的段 
		if( now1 <= tot && opt[i-1] == 'r' ) ++ now1;
		// 优先满足大的 
		// 如果a[now2] <= 1 说明对于所有的 i >= now2, 都满足a[i] <= 1 
		else if( now2 < now1 && a[now2] > 1 && opt[i-1] == 'b')	
			c += a[now2] - 2, now2 ++;
		// 如果蓝色和红色都不需要生成新的段，则用来填补以前的段 
		else if( c ) c --;
	}
	
	return now1 > tot && a[now2] <= 1 && !c; 
}

inline void update()
{
	ll res = 1; int num = tot + 1;
	
	int next = 1;
	for( int i = 1; i <= tot; i = next + 1 )
	{
		next = i; 
		while( a[next+1] == a[i] )
			next ++;
		
		res = res * c[next][i-1] %MOD;
		// 相当于在 i 个空中插入 next-i+1 个相同的球 
		num += ( next - i + 1 ) * ( ( a[i] << 1 ) -1 );
	} 
	
	res = res * c[num-1+_left][num-1] %MOD;
	ans = add( ans, res );
	
//	printf( "[UPD] left:%d, num:%d, res:%lld\n", _left, num, res );
}

void dfs( int u ) 
// 有序的枚举 
{
	if( _left < 0 ) return;
	if( check() ) update();

	if( tot ) _left --; tot ++;
	
	_left --; dfs( a[tot] = 1 ); _left ++;
	
	for( int i = 2; i <= u; i ++ )
	{
		_left -= ( i << 1 ) - 3;
		dfs( a[tot] = i ); 
		_left += ( i << 1 ) - 3; 
	}
	
	a[tot--] = 0;
	if( tot ) _left ++;
}
 
int main()
{
	scanf( "%d%d", &n, &k );
	init_c( 500 );
	
	cin>> opt;
	_left = n; dfs( 100 );
	
	printf( "%lld\n", add( ans, 1 ) );
	
	return 0;
}