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;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif


const int P = 1e9 + 7;
const int MAX = 300;
set<vector<int>> x;
vector<set<vector<int>>::iterator> zr,zb;
int res = 1;
int sil[MAX],odw[MAX];
int newt[MAX][MAX];
string z;
int n,k;
void add(vector<int> ak){
  auto pom = x.insert(ak);
  if(pom.SE){
    int mn = 1;
    int sum = 0;
    int sum2 = 0;
    R(i,SZ(ak)){
      sum += ak[i];
      sum2 += ak[i] * i;
      mn = (mn * odw[ak[i]]) % P;
    }
    int a = n + 2 + (sum - ak[0]) * 2 - 1;
    int b = 2 * sum2 + 2 * sum;
    if(a >= b){
      res += mn * sil[sum] % P * newt[a][b] % P;
      zr.PB(pom.FI);
      zb.PB(pom.FI);
    }
  }
}
void dod(vector<int> pom,int zak){
  R(i,SZ(pom))if(i != zak && (i == 0 || pom[i-1])){
    if(i)pom[i-1]--;
    pom[i]++;
    add(pom);
    pom[i]--;
    if(i)pom[i-1]++;
  }
  if(SZ(pom) != zak){
    if(SZ(pom))pom.back()--;
    pom.PB(1);
    add(pom);
  }
}
int pot(int a,int w){
  int r = 1;
  while(w){
    if(w & 1){
      r = r * a % P;
    }
    w/=2;
    a = a * a % P;
  }
  return r;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);

  sil[0] = 1;
  R(i,MAX-1){
    sil[i+1] = (i+1) * sil[i] % P;
  }
  R(i,MAX){
    odw[i] = pot(sil[i],P-2);
  }
  R(i,MAX)R(j,i+1){
    if(j == 0){
      newt[i][j] = 1;
    }else{
      newt[i][j] = newt[i-1][j-1] + newt[i-1][j];
      if(newt[i][j] >= P)
        newt[i][j] -= P;
    }
  }
  cin >> n >> k >> z;

  auto xx = x.insert(vector<int>());
  zr.PB(xx.FI);
  zb.PB(xx.FI);
  R(i,k){
    if(z[i] == 'r'){
      vector<set<vector<int>>::iterator> pom;
      swap(pom,zr);
      for(auto el:pom){
        dod(*el,1);
      }
    }else{
      vector<set<vector<int>>::iterator> pom;
      swap(pom,zb);
      for(auto el:pom){
        dod(*el,0);
      }
    }
  }
  cout << res % P << "\n";
}