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
/*
DPの典型手法とのことで以下のブログを参考にやった.
https://creep06.hatenablog.com/entry/20180927/1537996410
箱根DPとか未確定DPとかいうらしい.
多分このDPはDPによくある「i番目まで見たとき~」という情報に加えて
まだ未使用のものの数を状態に持たせるようなものであると考えられる.
今回の問題では, 上記のブログにある図のような二部グラフっぽいものを考えて
まだペアになっていないような頂点の数を状態として保持させている.
i番目までの頂点を見た時, 左側の頂点と右側の頂点それぞれをペアにしたり
しなかったりすることで状態を遷移することでDPをする.
結局この問題では以下のテーブルを定義することで解ける.
dp[i][j][k]: i番目の頂点のペアを見て, 左側の頂点がj個, 右側の頂点がk個残っているような場合の通り数
これを埋める場合O(N^3)かかるのだが, 左右どちらかの頂点がペアを作るときはその反対側の残っている頂点が
使用されるためどちらも同時に1減るし, どちらの頂点も使用しないならどちらの頂点の数も+1するため
状態におけるjとkは同じ値をとることになる.
そのためj!=kとなるdpテーブルは全て0になるので実際は以下のテーブルで解くことができる.
dp[i][j]: i番目の頂点のペアを見て, 左右の頂点がj個残っているような場合の数
こっちの場合はO(N^2)となるためより高速に動作する.
*/
#include<iostream>
#include<vector>
#include<string>
#define rep(i, start, end) for (int i = (int)start; i < (int)end; ++i)
#define rrep(i, start, end) for (int i = (int)start - 1; i >= end; --i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
template<typename T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return 0;}
template<typename T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return 0;}

template<typename T, long long MOD_VALUE>
class ModInt {
    static constexpr long long MOD = MOD_VALUE;
    private:
        T value_;
    public:
        ModInt() {}
        ModInt(const T& value) {if (value >= 0) {value_ = value % MOD;} else {T k = (MOD - 1 - value) / MOD; value_ = (value + k * MOD) % MOD;}}
        ModInt& operator+=(const ModInt& x)  {value_ += x.value_; if (value_ >= MOD) value_ -= MOD; return *this;}
        friend ModInt& operator+=(const T& x, const ModInt& y) {ModInt res(x); res.value_ += x.value_; if (res.value_ >= MOD) res.value_ -= MOD; return res;}
        ModInt& operator-=(const ModInt& x) {if (value_ < x.value_) value_ += MOD; value_ -= x.value_; return *this;}
        friend ModInt& operator-=(const T& x, const ModInt& y) {ModInt res(x); if (res.value_ < y.value_) res.value_ += MOD; res.value_ -= y.value_; return res;}
        ModInt& operator*=(const ModInt& x) {value_ = (value_ * x.value_) % MOD; return *this;}
        friend ModInt& operator*=(const T& x, const ModInt& y) {ModInt res(x); res.value_ = (res.value_ * y.value_) % MOD; return res;}
        const ModInt operator+(const ModInt& x) const {return ModInt(*this) += x;}
        friend const ModInt operator+(const T& x, const ModInt& y) {return ModInt(x) += y;}
        const ModInt operator-(const ModInt& x) const {return ModInt(*this) -= x;}
        friend const ModInt operator-(const T& x, const ModInt& y) {return ModInt(x) -= y;}
        const ModInt operator*(const ModInt& x) const {return ModInt(*this) *= x;}
        friend const ModInt operator*(const T& x, const ModInt& y) {return ModInt(x) *= y;}
        static ModInt modpow(ModInt x, long long y) {ModInt z = 1; while (y > 0) {if (y & 1) {z *= x;}x *= x; y /= 2;} return z;}
        ModInt& operator/=(const ModInt& x) {return *this *= modpow(x, MOD - 2);}
        const ModInt operator/(const ModInt& x) const {return ModInt(*this) /= x;}
        friend const ModInt operator/(const T& x, const ModInt& y) {return ModInt(x) /= y;}
        ModInt operator++(int) {ModInt tmp(*this); value_ = (value_ + 1 == MOD ? 0 : value_ + 1); return tmp;}
        ModInt operator--(int) {ModInt tmp(*this); value_ = (value_ - 1 < 0 ? MOD - 1 : value_ - 1); return tmp;}
        friend istream& operator>>(istream& stream, ModInt& x) {stream >> x.value_; x.value_ %= MOD; return stream;}
        friend ostream& operator<<(ostream& stream, const ModInt& x) {stream << x.value_; return stream;}
};

using mint = ModInt<ll, 1000000007>;

void solve1(int N, const vector<char>& C) {
    vector<vector<vector<mint>>> dp(N + 1, vector<vector<mint>>(N + 1, vector<mint>(N + 1, 0)));
    dp[0][0][0] = 1;
    rep(i, 0, N) rep(j, 0, N + 1) rep(k, 0, N + 1) {
        if (C[i] == 'D') {
            if (j >= 1 && k >= 1) {
                dp[i + 1][j - 1][k - 1] += dp[i][j][k] * j * k;
            }
            dp[i + 1][j][k] += dp[i][j][k] * j;
        }
        else if (C[i] == 'U') {
            dp[i + 1][j][k] += dp[i][j][k] * k;
            if (j < N && k < N) {
                dp[i + 1][j + 1][k + 1] += dp[i][j][k];
            }
        }
        else {
            if (j < N && k < N) {
                dp[i + 1][j][k] += dp[i][j][k];
            }
        }
    }
    cout << dp[N][0][0] << endl;
    return;
}

void solve2(int N, const vector<char>& C) {
    vector<vector<mint>> dp(N + 1, vector<mint>(N + 1, 0));
    dp[0][0] = 1;
    rep(i, 0, N) rep(j, 0, N) {
        if (C[i] == 'D') {
            if (j >= 1) {
                dp[i + 1][j - 1] += dp[i][j] * j * j;
            }
            dp[i + 1][j] += dp[i][j] * j;
        }
        else if (C[i] == 'U') {
            dp[i + 1][j] += dp[i][j] * j;
            dp[i + 1][j + 1] += dp[i][j];
        }
        else {
            dp[i + 1][j] += dp[i][j];
        }
    }
    cout << dp[N][0] << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<char> C(N);
    for (auto& c : C) {
        cin >> c;
    }
    // solve1(N, C);
    solve2(N, C);
    return 0;
}
