22476번 - Hakone 다국어

日本のお正月の風物詩に箱根駅伝があります。箱根駅伝は、各チーム 10 人の走者が中継所ごとに襷をつなぎながらゴールを目指すというものです。テレビの放送では中継所で各チームの通過順位と共に前の中継所からの順位変動が表示されます。そこで、それを見て前の中継所の各チームの通過順として考えられるものが何通りあるか答えてください。ありえた通過順の数は非常に大きくなりうるので、1,000,000,007 で割った余りで答えて下さい。

入力は以下の形で与えられます

n
c1
c2
...
cn

1行目にはチーム数を表す数字 n (1 ≤ n ≤ 200) が、続く n 行には 1 位から順に前の中継所からの順位変動 c_i ('D' なら順位が落ちてる、'U' なら順位が上がってる、'-' なら順位が変わってない) が書いてあります。

前の中継所でありえた通過順が何通りかを、 1,000,000,007 で割ったあまりで 1 行で出力して下さい。