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

"""
Writer: SPD_9X2
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2439

1位から順番に見ていく。
-ならそこの順位に決めざるを得ない

Uなら、左に空いた空きマスから1つ選んでそこに入れる(空きマスは減る)
Dなら、…？

dpであることは分かっている
重要なのはどの状態をまとめるか…

-は関係ないので無視してUDだけの問題にする
UDの列に通し番号を付ける。Uはそれより右に、Dは左にもっていかなくてはならない
そのような並び替えが構成できなくなるのは、左にもとよりUが多い場合・・・

Uだけの入れ方を考えてみる(Dはどこに入っても構わない)
左から見ていくと、入れる・入れないを決め、今までに出たUの中から1つ選んで入れればよい
→ただのdpで解ける

Dだけの入れ方も同様に分かる

あらかじめU,Dにおいてdpをしておく？

udp[左からi番目にUが入る場合のUの入り方][j][k] =
ん～？？？？？

=====解説を見た=====

Uならば、それより右に入れなきゃいけない→保留枠に入れ、Uのあったマスを開けておく
Dならば、そこにあったDを左の空きますにぶち込み、保留の中から1つUを選んでぶち込む or　空きますにする
→空きマスは1つ減る or 減らない

空きマスの数 = 保留の数なので、 O(N**2)で解ける

"""

n = int(input())

dp = [0] * (n+1)
dp[0] = 1
mod = 10**9+7

for loop in range(n):

    c = input()
    ndp = [0] * (n+1)
    if c == "-":
        continue

    
    elif c == "U":
        for i in range(n+1):

            if i != n: #保留に入れて空きますにする
                ndp[i+1] = dp[i]
                ndp[i+1] %= mod

            #保留に入れ、保留から1つ取り出して入れる

            ndp[i] += dp[i] * i
            ndp[i] %= mod
            

    else:
        for i in range(0,n+1):

            if i != 0: #そこにあったのは左の空きますに移動 & そのマスに保留からぶち込む
                ndp[i-1] += dp[i] * i * i
                ndp[i-1] %= mod

            #そこにあったのは左の空きますに、そこは空きますにする

            ndp[i] += dp[i] * i
            ndp[i] %= mod
    

    dp = ndp
    #print (dp)

print (dp[0])

