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>
//clock_t t=clock();
namespace my_std{
	using namespace std;
	#define pii pair<int,int>
	#define fir first
	#define sec second
	#define MP make_pair
	#define rep(i,x,y) for (int i=(x);i<=(y);i++)
	#define drep(i,x,y) for (int i=(x);i>=(y);i--)
	#define go(x) for (int i=head[x];i;i=edge[i].nxt)
	#define templ template<typename T>
	#define sz 2333
	#define mod 1000000007ll
	typedef long long ll;
	typedef double db;
//	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//	templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
	templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
	templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
	templ inline void read(T& t)
	{
		t=0;char f=0,ch=getchar();double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
		if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
		t=(f?-t:t);
	}
//	template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
	char __sr[1<<21],__z[20];int __C=-1,__zz=0;
	inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
	inline void print(register int x)
	{
		if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
		while(__z[++__zz]=x%10+48,x/=10);
		while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
	}
//	void file()
//	{
//		#ifdef NTFOrz
//		freopen("a.in","r",stdin);
//		#endif
//	}
//	inline void chktime()
//	{
//		#ifdef NTFOrz
//		cout<<(clock()-t)/1000.0<<'\n';
//		#endif
//	}
	#ifdef mod
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
	ll inv(ll x){return ksm(x,mod-2);}
	#else
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
	#endif
//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

ll fac[sz],_fac[sz];
void init(){_fac[0]=fac[0]=1;rep(i,1,sz-1) _fac[i]=inv(fac[i]=fac[i-1]*i%mod);}
ll C(int n,int m){return n>=m&&m>=0?fac[n]*_fac[m]%mod*_fac[n-m]%mod:0;}

int n,m;
char s[sz];
int a[sz],K;
int vis[sz],ed[sz];
ll ans;

bool check()
{
	rep(i,1,m) vis[i]=0;
	int l=1,r=1,c=0;
	rep(i,1,K)
	{
		if (a[i]==1) { ++c; continue; }
		while (l<=m&&(vis[l]||s[l]=='b')) ++l;
		chkmax(r,l+1);
		while (r<=m&&(vis[r]||s[r]=='r')) ++r;
		if (r>m) return 0;
		vis[l]=vis[r]=1;ed[i]=r;
	}
	int cc=c;
	rep(i,1,m) if (cc&&s[i]=='r'&&!vis[i]) vis[i]=1,--cc;
	if (cc) return 0;
	int pos=1;
	rep(i,1,K)
	{
		if (a[i]==1) break;
		chkmax(pos,ed[i]);
		cc=a[i]-2;
		while (pos<=m&&cc) cc-=(!vis[pos]),++pos;
		if (cc) return 0;
	}
	return 1;
}
void work()
{
	if (!check()) return;
	ll ret=fac[K];
	for (int l=1,r;l<=K;l=r+1)
	{
		for (r=l;r<K&&a[r+1]==a[r];++r);
		ret=ret*_fac[r-l+1]%mod;
	}
	int sum=K-1; rep(i,1,K) sum+=(a[i]==1?1:a[i]*2-3);
	int c=2; rep(i,1,K) c+=2*(a[i]!=1);
	ret=ret*C(n+c-1,sum+c-1)%mod;
	(ans+=ret)%=mod;
}

void dfs(int m,int lst,int sum)
{
	if (K-1+sum>n) return;
	work();
	drep(i,min(m,lst),1) a[++K]=i,dfs(m-i,i,sum+(i==1?1:i*2-3)),a[K--]=0;
}

int main()
{
	init();
	read(n),read(m);
	cin>>(s+1);
	dfs(m,m,0);
	cout<<ans;
	return 0;
}