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
#include <iostream>
#include <fstream>
#include <iomanip>
#include <climits>
#include <limits>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <unordered_map>
#include <random>
#include <cmath>
#include <complex>

using namespace std;

typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;

const int INFL = (int)1e9;
const ll INFLL = (ll)1e18;
const double INFD = numeric_limits<double>::infinity();
const double PI = 3.14159265358979323846;
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loopll(i, n) for(ll i = 0; i < (ll)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopll1(i, n) for(ll i = 1; i <= (ll)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Looprll(i, n) for(ll i = (ll)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
#define Looprll1(i, n) for(ll i = (ll)n; i >= 1; i--)
#define Loopitr(itr, container) for(auto itr = container.begin(); itr != container.end(); itr++)
#define printv(vector) Loop(i, vector.size()) { cout << vector[i] << " "; } cout << endl;
#define printmx(matrix) Loop(i, matrix.size()) { Loop(j, matrix[i].size()) { cout << matrix[i][j] << " "; } cout << endl; }
#define rnd(d) (ll)((double)(d) + (d >= 0 ? 0.5 : -0.5))
#define floorsqrt(x) ((ll)sqrt((double)x) + ((ll)sqrt((double)x) * (ll)sqrt((double)x) <= (ll)(x) ? 0 : -1))
#define ceilsqrt(x) ((ll)sqrt((double)x) + ((ll)x <= (ll)sqrt((double)x) * (ll)sqrt((double)x) ? 0 : 1))
#define ceildiv(a, b) ((ll)(a) / (ll)(b) + ((ll)(a) % (ll)(b) == 0 ? 0 : 1))
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)

/*******************************************************/

namespace mod_op {

	const ll MOD = (ll)1e9 + 7;

	class Extended_Euclid {
	private:
		ll m, n;
		vvll mx_multiply(vvll mx1, vvll mx2) {
			vvll ret(mx1.size(), vll(mx2[0].size(), 0));
			Loop(i, mx1.size()) {
				Loop(j, mx1[0].size()) {
					Loop(k, mx2[0].size()) {
						ret[i][j] += mx1[i][k] * mx2[k][j];
					}
				}
			}
			return ret;
		}
	public:
		// solve x, y s.t. mx + ny = gcd(m,n)
		ll x, y, gcd;
		Extended_Euclid(ll M, ll N) {
			m = M;
			n = N;
			vll r(100), k(100);
			bool swapflag = false, m_negflag = false, n_negflag = false;
			if (m < n) { swap(m, n); swapflag = true; }
			if (m < 0) { m *= -1; m_negflag = true; }
			if (n < 0) { n *= -1; n_negflag = true; }
			r[0] = m;
			r[1] = n;
			int h = 1;
			while (1) {
				k[h - 1] = r[h - 1] / r[h];
				r[h + 1] = r[h - 1] % r[h];
				if (r[h + 1] == 0) break;
				h++;
			}
			gcd = r[h];
			vvll mx1 = { { 0, 1 },{ 1, (-1) * k[h - 1] } };
			Loopr(i, h - 1) {
				vvll mx2 = { { 0, 1 },{ 1, (-1) * k[i] } };
				mx1 = mx_multiply(mx1, mx2);
			}
			x = mx1[0][0];
			y = mx1[0][1];
			if (n_negflag) { n *= -1; y *= -1; }
			if (m_negflag) { m *= -1; x *= -1; }
			if (swapflag) { swap(m, n); swap(x, y); }
		}
	};

	class modll {
	private:
		ll val;
		inline ll modify(ll x) { ll ret = x % MOD; if (ret < 0) ret += MOD; return ret; }
		inline ll inv(ll x) { if (x == 0) return 1 / x; Extended_Euclid ee(x, -MOD); return modify(ee.x); }
	public:
		modll(ll init = 0) { val = modify(init); return; }
		modll(const modll& another) { val = another.val; return; }
		inline modll& operator=(const modll &another) { val = another.val; return *this; }
		inline modll operator+(const modll &x) { return (val + x.val) % MOD; }
		inline modll operator-(const modll &x) { return (val - x.val) % MOD; }
		inline modll operator*(const modll &x) { return (val * x.val) % MOD; }
		inline modll operator/(const modll &x) { return (val * inv(x.val)) % MOD; }
		inline modll& operator+=(const modll &x) { val = (val + x.val) % MOD; return *this; }
		inline modll& operator-=(const modll &x) { val = (val - x.val) % MOD; return *this; }
		inline modll& operator*=(const modll &x) { val = (val * x.val) % MOD; return *this; }
		inline modll& operator/=(const modll &x) { val = (val * inv(x.val)) % MOD; return *this; }
		friend inline istream& operator >> (istream &is, modll& x) { is >> x.val; return is; }
		friend inline ostream& operator << (ostream &os, modll& x) { os << x.val; return os; }
		ll get_val() { return val; }
	};

	modll pow(modll n, ll p) {
		modll ret;
		if (p == 0) ret = 1;
		else if (p == 1) ret = n;
		else {
			ret = pow(n, p / 2);
			ret *= ret;
			if (p % 2 == 1) ret *= n;
		}
		return ret;
	}
}

using namespace mod_op;
typedef vector<modll> vmodll;
typedef vector<vector<modll>> vvmodll;

int main() {
	const int N = 201;
	int n; cin >> n;
	vector<char> a(n);
	Loop(i, n) cin >> a[i];
	vvmodll dp(N, vmodll(N, 0));
	dp[0][0] = 1;
	Loop(i, n) {
		vvmodll dpbuf(N, vmodll(N, 0));
		Loop(j, N) {
			Loop(k, N) {
				if (a[i] == 'U') {
					if (j > 0) dpbuf[j][k] += dp[j][k] * j;
					if (j + 1 < N && k + 1 < N) dpbuf[j + 1][k + 1] += dp[j][k];
				}
				else if (a[i] == 'D') {
					if (j - 1 >= 0 && k - 1 >= 0) dpbuf[j - 1][k - 1] += dp[j][k] * j * k;
					if (k > 0) dpbuf[j][k] += dp[j][k] * k;
				}
				else {
					dpbuf[j][k] = dp[j][k];
				}
			}
		}
		dp = dpbuf;
	}
	cout << dp[0][0] << endl;
}
