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<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
#define SIZE 100000
ll inv[SIZE + 1];
ll kai[SIZE + 1];
ll invkai[SIZE + 1];
void invinit()
{
	inv[1] = 1;
	for (int i = 2; i <= SIZE; i++)
	{
		inv[i] = mod - (mod / i)*inv[mod%i] % mod;
	}
	kai[0] = invkai[0] = 1;
	for (int i = 1; i <= SIZE; i++)
	{
		kai[i] = kai[i - 1] * i%mod;
		invkai[i] = invkai[i - 1] * inv[i] % mod;
	}
}
ll com(ll a, ll b)
{
	if (b < 0 || a < b)return 0;
	return (invkai[b] * invkai[a - b]) % mod*kai[a] % mod;
}
ll dp[100][100][100];
int main()
{
	int num, kai;
	scanf("%d%d", &num, &kai);
	string s;
	cin >> s;
	invinit();
	ll ans = 0;
	for (int p = 0; p <= kai / 2; p++)
	{
		for (int q = 0; q <= kai - p * 2; q++)
		{
			if (p + q + (p + q - 1)>num)continue;
			int d[100];
			fill(d, d + 100, 0);
			queue<int>que;
			int np = 0;
			for (int i = 0; i < s.size(); i++)
			{
				if (np == p)break;
				if (s[i] == 'r')que.push(i);
				else
				{
					if (que.empty())continue;
					int z = que.front();
					que.pop();
					d[z] = 1, d[i] = 2;
					np++;
				}
			}
			if (np != p)continue;
			int nq = 0;
			for (int i = 0; i < s.size(); i++)
			{
				if (nq == q)break;
				if (d[i] == 0 && s[i] == 'r')d[i] = 3, nq++;
			}
			if (nq != q)continue;
			//printf("%d %d ", p, q);
			//for (int i = 0; i < kai; i++)printf("%d", d[i]); printf("\n");
			vector<int>v;
			int cnt = 0;
			for (int i = s.size() - 1; i >= 0; i--)
			{
				if (d[i] == 0)cnt++;
				if (d[i] == 2)v.push_back(cnt);
			}
			for (int i = 0; i <= v.size(); i++)for (int j = 0; j <= cnt + 1; j++)for (int k = 0; k <= cnt + 1; k++)dp[i][j][k] = 0;
			dp[0][0][0] = 1;
			for (int i = 0; i <= v.size(); i++)
			{
				for (int j = 0; j <= cnt; j++)
				{
					for (int k = 0; k <= cnt; k++)
					{
						if (dp[i][j][k] == 0)continue;
						dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i][j][k]) % mod;
						for (int l = 1; i + l <= v.size(); l++)
						{
							if (v[i + l - 1] < j + k*l)break;
							dp[i + l][j + k*l][k + 1] = (dp[i + l][j + k*l][k + 1] + dp[i][j][k] * com(i + l, l)) % mod;
						}
					}
				}
			}
			ll t[100];
			for (int i = 0; i <= cnt; i++)t[i] = dp[v.size()][i][cnt + 1];
			//for (int i = 0; i <= cnt; i++)printf(" %lld", t[i]); printf("\n");
			ll sum = 0;
			for (int i = 0; i <= cnt; i++)
			{
				int ned = q + p + 2 * i + (p + q - 1);
				int add = q + 3 * p + 2 * i + (p + q + 1);
				if (ned > num)continue;
				sum += t[i] * com(num - ned + add - 1, add - 1);
				sum %= mod;
			}
			//printf(" %lld\n", sum);
			ans = (ans + sum*com(p + q, p)) % mod;
		}
	}
	printf("%lld\n", ans);
}