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:
//Zory-2020
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// typedef __int128 ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define FR first
#define SE second
#define MP make_pair
#define PB push_back
#define vc vector
#define db double
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define bin(x) (1ll<<(x))
#define fo(i,l,r) for(int i=(l),I=(r);i<=I;i++)
#define fd(i,r,l) for(int i=(r),I=(l);i>=I;i--)
#define mem(x,val) memset(x,val,sizeof x)
#define Swap(a,b,n) for(int I=0;I<=n;I++) swap(a[I],b[I])
#define PC __builtin_popcountll
#ifdef DEBUG
	#define debug(A,args...) fprintf(stderr,A,##args)
#else
	#define debug(A,args...) printf("")
#endif
#define deb debug("line %d\n",__LINE__)
namespace mine
{
	ll qread()
	{
		ll ans=0,f=1;char c=getchar();
		while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
		while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
		return ans*f;
	}
	void write(ll num){if(num<0) putchar('-'),num=-num;if(num>=10) write(num/10);putchar('0'+num%10);}
	void write1(ll num){write(num);putchar(' ');}
	void write2(ll num){write(num);putchar('\n');}
	template<typename T>inline bool chmax(T&a,const T&b){return a<b?a=b,1:0;}
	template<typename T>inline bool chmin(T&a,const T&b){return a>b?a=b,1:0;}
	ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
	bool IN(ll x,ll l,ll r){return l<=x and x<=r;}
	void GG(){puts("-1");exit(0);}
	
	const db eps=1e-8;
	const int INF=0x3f3f3f3f;
	const int MOD=1e9+7;
	int mm(const int x){return x>=MOD?x-MOD:x;}
	template<typename T> void add(T &x,const int &y){x=(x+y>=MOD?x+y-MOD:x+y);}
	ll qpower(ll x,ll e,int mod=MOD){ll ans=1;while(e){if(e&1)ans=ans*x%mod;x=x*x%mod;e>>=1;}return ans;}
	ll invm(ll x){return qpower(x,MOD-2);}
	const int M=1e3+10;
	ll fac[M],facinv[M],Inv[M];ll C(int n,int m){return n<0 or m<0 or n<m?0:fac[n]*facinv[m]%MOD*facinv[n-m]%MOD;}
	void PRE()
	{
		fac[0]=1;fo(i,1,M-1) fac[i]=fac[i-1]*i%MOD;
		facinv[M-1]=invm(fac[M-1]);fd(i,M-1,1) facinv[i-1]=facinv[i]*i%MOD;
		Inv[1]=1;fo(i,2,M-1) Inv[i]=(MOD-MOD/i)*Inv[MOD%i]%MOD;
	}
	const int N=300+10;
	//------------------FIXED------------------
	char str[N];int pos[N],blu[N];bool inB[N];
	ll Bin[N];
	int up[N],dp[N][N][N];
	void main()
	{
		Bin[0]=1;fo(i,1,N-1) Bin[i]=Bin[i-1]*2%MOD;
		int n=qread(),m=qread();scanf("%s",str+1);int ans=0;
		fo(A,0,m/2)
		{
			int R=0;mem(inB,0);
			fo(i,1,m) if(str[i]=='r')
			{
				if(R==A) break;
				bool ok=0;fo(j,i+1,m) if(str[j]=='b' and !inB[j]) {inB[j]=1,pos[++R]=j,ok=1;break;}
				if(!ok) break;
			}if(R<A) break;
			
			fo(B,0,m)
			{
				int cc=0;fo(i,1,m) if(str[i]=='r') cc++,blu[i]=blu[i-1]+(cc>A+B); else blu[i]=blu[i-1]+(!inB[i]);if(cc<A+B) break;
				up[A+1]=0,pos[A+1]=m;fd(i,A,1) up[i]=up[i+1]+(blu[pos[i+1]]-blu[pos[i]])+1;reverse(up+1,up+A+1);
				
				dp[0][0][0]=1;fo(ln,1,m) fo(i,0,A) fo(S,0,up[i]) dp[ln][i][S]=0;
				fo(ln,1,m) fo(i,0,A) fo(S,0,min(up[i],up[A]-ln*(A-i))) if(dp[ln-1][i][S])
					for(int ad=0;i+ad<=A and S+ad*ln<=up[i+ad];ad++)
						add(dp[ln][i+ad][S+ad*ln],dp[ln-1][i][S]*facinv[ad]%MOD);
				fo(S,0,up[A]) if(dp[m][A][S])
				{
					ll feikong=2*S+2*B-1,kekong=A*2+2;//隔板法
					add(ans, dp[m][A][S]*C(n+kekong-1, feikong+kekong-1 )%MOD*fac[A+B]%MOD*facinv[B]%MOD );
				}
			}
		}
		write(ans);
	}
};//����������
signed main()
{
	#ifdef DEBUG
	freopen("a.in","r",stdin);
	//freopen("z.txt","r",stdin);
	//freopen("a.out","w",stdout);
	#endif
	srand(time(0));
	mine::PRE();//����Ԥ����ģ����
	mine::main();
	debug("\n---------------------Zory---------------------\nTime: %.2lf s",1.0*clock()/CLOCKS_PER_SEC);
}