Hakone Ekiden is one of the Japanese New Year's traditions. In Hakone Ekiden, 10 runners from each team aim for the goal while connecting the sashes at each relay station. In the TV broadcast, the ranking change from the previous relay station is displayed along with the passing order of each team at the relay station. So, look at it and tell us how many possible passage orders for each team at the previous relay station. The number of possible transit orders can be very large, so answer by the remainder divided by 1,000,000,007.



Input

The input is given in the form:

> n
> c1
> c2
> ...
> cn
>

The number n (1 ≤ n ≤ 200) representing the number of teams is on the first line, and the ranking changes from the previous relay station in order from the first place on the following n lines. If it is'`U`', the ranking is up, if it is'`-`', the ranking is not changed) is written.

Output

Please output in one line by dividing the number of passages that could have been the previous relay station by 1,000,000,007.

Examples

Input

3
-
U
D


Output

1


Input

5
U
U
-
D
D


Output

5


Input

8
U
D
D
D
D
D
D
D


Output

1


Input

10
U
D
U
D
U
D
U
D
U
D


Output

608


Input

2
D
U


Output

0
// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
// #include<deque>
// #include<multiset>
// #include<bitset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

// #undef DEBUG
// #define DEBUG
// DEBUG {{{
#include <array>
#include <deque>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <valarray>
#include <vector>
// clang-format off
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream &o, tuple<T...> const &t){ o << "("; _ot<0>(o, t); o << ")"; return o; }
template<class T, class U> ostream & operator<<(ostream &o, pair<T, U> const &p) { o << "(" << p.first << ", " << p.second << ")"; return o; }
template < class T > ostream &operator<<(ostream &o, const stack<T> &a) { o << "{"; for(auto tmp = a; tmp.size(); tmp.pop()) o << (a.size() == tmp.size() ? "" : ", ") << tmp.top(); o << "}"; return o; }
template <class T, class Container, class Compare > ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> a) { os << "{ (top) "; while(a.size()) os << a.top() << (a.size() == 1 ? "" : ", "), a.pop(); os << " }"; return os; }
template <class T, class Container > ostream &operator<<(ostream &os, queue<T, Container> a) { os << "{ "; while(a.size()) os << a.front() << (a.size() == 1 ? "" : ", "), a.pop(); os << " }"; return os; }
#ifdef DEBUG
#if !defined(DEBUG_OUT)
#define DEBUG_OUT cerr
#endif
#if !defined(DEBUG_LEFT)
#define DEBUG_LEFT "\e[1;36m"
#endif
#if !defined(DEBUG_RIGHT)
#define DEBUG_RIGHT ":\e[m"
#endif
#define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);DEBUG_OUT<<DEBUG_LEFT<<__LINE__ << DEBUG_RIGHT << " " <<#__VA_ARGS__<<" = "<<__debug_tap<<endl;}()
template < class T > inline void dump2D(T &d, size_t sizey, size_t sizex) { for(size_t i = 0; i < sizey; i++) { DEBUG_OUT << "\t"; for(size_t j = 0; j < sizex; j++) DEBUG_OUT << d[i][j] << (j + 1 == sizex ? "" : "\t"); DEBUG_OUT << endl; } }
template < class T, class = typename iterator_traits< decltype(begin(T())) >::value_type, class = typename enable_if<!is_same<T, string>::value>::type > ostream &operator<<(ostream &o, const T &a) { o << "{"; for(auto ite = begin(a); ite != end(a); ++ite) o << (ite == begin(a) ? "" : ", ") << *ite; o << "}"; return o; }
#else
#define dump(...) (42)
#define dump2D(...) (42)
template < class T, class = typename iterator_traits< decltype(begin(T())) >::value_type, class = typename enable_if<!is_same<T, string>::value>::type > ostream &operator<<(ostream &o, const T &a) { for(auto ite = begin(a); ite != end(a); ++ite) o << (ite == begin(a) ? "" : " ") << *ite; return o; }
#endif
// clang-format on
// }}}


/// --- ModInt Library {{{ ///
#include <ostream>
template < ll mod = (ll) 1e9 + 7 >
struct ModInt {
  // math {{{
  static inline ll extgcd(ll a, ll b, ll &x, ll &y) {
    ll d;
    return b == 0 ? (x = 1, y = 0, a) : (d = extgcd(b, a % b, y, x), y -= a / b * x, d);
  }
  static inline ll modinv(ll a) {
    ll x = 0, y = 0;
    extgcd(a, mod, x, y);
    if(x < 0) x += mod;
    return x;
  }
  static inline ll modpow(ll a, ll b) {
    if(b < 0) b = -b, a = modinv(a);
    ll r = 1;
    a %= mod;
    while(b) {
      if(b & 1) r = r * a % mod;
      a = a * a % mod;
      b >>= 1;
    }
    return r;
  }
  // }}}

  ll val;
  constexpr ModInt() : val(0) {}
  constexpr ModInt(ll t) {
    val = t % mod;
    if(val < 0) val += mod;
  }

private:
  // strict constructor
  constexpr ModInt(ll t, int) : val(t) {}

public:
  template < class T >
    explicit operator T() {
      return T(val);
    }
  // ModInt <arithmetic-operator>[=] ModInt {{{
  ModInt operator+(ModInt const &rhs) const {
    ModInt tmp = *this;
    tmp += rhs;
    return tmp;
  }
  ModInt operator-(ModInt const &rhs) const {
    ModInt tmp = *this;
    tmp -= rhs;
    return tmp;
  }
  ModInt operator*(ModInt const &rhs) const {
    ModInt tmp = *this;
    tmp *= rhs;
    return tmp;
  }
  ModInt operator/(ModInt const &rhs) const {
    ModInt tmp = *this;
    tmp /= rhs;
    return tmp;
  }
  ModInt &operator+=(ModInt const &rhs) {
    val = val + rhs.val;
    if(val >= mod) val -= mod;
    return *this;
  }
  ModInt &operator-=(ModInt const &rhs) { return *this += -rhs; }
  ModInt &operator*=(ModInt const &rhs) {
    val = val * rhs.val % mod;
    return *this;
  }
  ModInt &operator/=(ModInt const &rhs) { return *this *= rhs.inv(); }
  // }}}
  // increment, decrement {{{
  ModInt operator++(int) {
    ModInt tmp = *this;
    val = val + 1;
    if(val >= mod) val = 0;
    return tmp;
  }
  ModInt operator--(int) {
    ModInt tmp = *this;
    val = val == 0 ? mod - 1 : val - 1;
    return tmp;
  }
  ModInt &operator++() {
    val = val + 1;
    if(val >= mod) val = 0;
    return *this;
  }
  ModInt &operator--() {
    val = val == 0 ? mod - 1 : val - 1;
    return *this;
  }
  // }}}
  ModInt operator-() const { return ModInt(val == 0 ? 0 : mod - val, 0); }
  // ModInt <arithmetic-operator>[=] T {{{
  template < typename T >
    ModInt operator+(T const &rhs) const {
      return ModInt(val + rhs % mod);
    }
  template < typename T >
    ModInt operator-(T const &rhs) const {
      return ModInt(mod + val - rhs % mod);
    }
  template < typename T >
    ModInt operator*(T const &rhs) const {
      return ModInt(val * (rhs % mod));
    }
  template < typename T >
    ModInt operator/(T const &rhs) const {
      return ModInt(val * modinv(rhs));
    }
  template < typename T >
    ModInt &operator+=(T const &rhs) {
      val = (mod + val + rhs % mod) % mod;
      return *this;
    }
  template < typename T >
    ModInt &operator-=(T const &rhs) {
      val = (mod + val - rhs % mod) % mod;
      return *this;
    }
  template < typename T >
    ModInt &operator*=(T const &rhs) {
      val = val * (mod + rhs % mod) % mod;
      return *this;
    }
  template < typename T >
    ModInt &operator/=(T const &rhs) {
      val = val * modinv(rhs, mod) % mod;
      return *this;
    }
  // }}}
  ModInt inv() const { return ModInt(modinv(val), 0); }
  ModInt operator~() const { return inv(); }
  friend ostream &operator<<(ostream &os, ModInt const &mv) {
    os << mv.val;
    return os;
  }
  // T <arithmetic-operator> ModInt {{{
  friend constexpr ModInt operator+(ll a, ModInt const &mv) {
    return ModInt(a % mod + mv.val);
  }
  friend constexpr ModInt operator-(ll a, ModInt const &mv) {
    return ModInt(a % mod - mv.val);
  }
  friend constexpr ModInt operator*(ll a, ModInt const &mv) {
    return ModInt((mod + a % mod) * mv.val % mod, 0);
  }
  friend constexpr ModInt operator/(ll a, ModInt const &mv) {
    return ModInt((mod + a % mod) * modinv(mv.val) % mod, 0);
  }
  // }}}
  // power {{{
  ModInt operator^(ll x) const { return pow(*this, x); }
  ModInt &operator^=(ll x) {
    val = modpow(val, x);
    return *this;
  }
  friend ModInt pow(ModInt x, ll y) { return ModInt(modpow(x.val, y), 0); }
  // }}}
};
/// }}}--- ///

using mint = ModInt<>;

mint dp[201][201]; // [i][j] := i個決めた時，古い順はj個下に繋げられるようになっているときの場合の数

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n = 0, m; cin >> m;
  vector<int> up;
  for(int i = 0; i < m; i++) {
    char c;
    cin >> c;
    if(c == 'D') n++, up.emplace_back(1); // 上へと結ぶ，という意味で入れ替わっている
    if(c == 'U') n++, up.emplace_back(0);
  }

  dp[0][0] = 1;
  for(int i = 0; i < n; i++) {
    for(int j = 0; j <= i; j++) {
      // jだけ，新しい順位を下につなげられる
      if(up[i]) {
        // これ自体はj個から選ぶ
        if(j >= 1) {
          // 古い順の (i+1) を
          // 下に向けるとき
          dp[i+1][j] += dp[i][j] * j;
          // 上に向けるとき
          dp[i+1][j-1] += dp[i][j] * j * j;
        }
      } else {
        // 下に向けるとき
        dp[i+1][j+1] += dp[i][j];
        // 上に向けるとき
        if(j >= 1) dp[i+1][j] += dp[i][j] * j;
      }
    }
  }

  cout << dp[n][0] << endl;
  return 0;
}

