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>
char s[128];
bool vis[128];
int a[128];
int wz[128];
int num[128];
int n,k;
int jc[512],injc[512];
int answer=0;
bool sol(int m)
{
	for(int i=0;i<k;i++)
	{
		vis[i]=false;
	}
	int now=0;
	for(int i=0;i<m;i++)
	{
		while(s[now]=='b'||vis[now])
		{
			now++;
			if(now==k)
			{
				return false;
			}
		}
		wz[i]=now;
		vis[now]=true;
	}
	now=0;
	for(int i=0;i<m;i++)
	{
		if(a[i]==1)
		{
			break;
		}
		while(s[now]=='r'||vis[now]||now<wz[i])
		{
			now++;
			if(now==k)
			{
				return false;
			}
		}
		wz[i]=now;
		vis[now]=true;
	}
	now=0;
	for(int i=0;i<m;i++)
	{
		if(a[i]<=2)
		{
			break;
		}
		int rm=a[i]-2;
		while(rm--)
		{
			while(vis[now]||now<wz[i])
			{
				now++;
				if(now==k)
				{
					return false;
				}
			}
			wz[i]=now;
			vis[now]=true;
		}
	}
	for(int i=1;i<=k;i++)
	{
		num[i]=0;
	}
	for(int i=0;i<m;i++)
	{
		num[a[i]]++;
	}
	int ans=jc[m];
	for(int i=1;i<=k;i++)
	{
		ans=(long long)ans*injc[num[i]]%1000000007;
	}
	int nums=m+1;
	int nume=2;
	for(int i=0;i<m;i++)
	{
		if(a[i]==1)
		{
			nums++;
		}
		else
		{
			nume+=2;
			nums+=(a[i]<<1)-1;
		}
	}
	int u=n+nume-1;
	int d=nums-1;
	if(d>u)
	{
		return false;
	}
	ans=(long long)ans*jc[u]%1000000007;
	ans=(long long)ans*injc[d]%1000000007;
	ans=(long long)ans*injc[u-d]%1000000007;
	answer+=ans;
	if(answer>=1000000007)
	{
		answer-=1000000007;
	}
	return true;
}
void dfs(int wz,int mx,int rm)
{
	if(!sol(wz))
	{
		return;
	}
	if(mx>rm)
	{
		mx=rm;
	}
	for(int i=1;i<=mx;i++)
	{
		a[wz]=i;
		dfs(wz+1,i,rm-i);
	}
}
int main()
{
	injc[1]=1;
	for(int i=2;i<=300;i++)
	{
		injc[i]=(long long)1000000007/i*injc[1000000007%i]%1000000007;
		injc[i]=1000000007-injc[i];
	}
	jc[0]=1;
	injc[0]=1;
	for(int i=1;i<=300;i++)
	{
		jc[i]=(long long)jc[i-1]*i%1000000007;
		injc[i]=(long long)injc[i-1]*injc[i]%1000000007;
	}
	scanf("%d%d",&n,&k);
	scanf("%s",s);
	dfs(0,k,k);
	printf("%d\n",answer);
	return 0;
}