問題文

横一列に並んだ $N$ 本の棒があります。 棒には左から順に棒 $1, 2, \dots, N$ と番号がついており、整数 $i$ の番号がついた棒を「棒 $i$」と呼びます。 正整数 $N$ とL,R,U,.からなる $N$ 文字の文字列 $S$ が与えられます。 あなたは一直線上に並んだ $N$ 本の棒をそれぞれ「左に倒す、右に倒す、倒さない」のいずれかの状態にすることができます。

$N$ 本の棒の倒し方が以下すべての条件に従っているとき、それは正しいと呼びます。 以下の文章では、$i$ は $1 \le i \le N$ を満たす整数とします。

• 右に倒れている棒であって、その右隣の棒が左に倒れているものが存在しないこと。(より厳密には、棒 $k$ が右に倒れ、かつ棒 $k+1$ が左に倒れているような $1 \le k \le N-1$ を満たす整数 $k$ が存在してはならない)
• $S$ の $i$ 番目の文字がLであるすべての $i$ について、棒 $i$ が左に倒れていること。
• $S$ の $i$ 番目の文字がRであるすべての $i$ について、棒 $i$ が右に倒れていること。
• $S$ の $i$ 番目の文字がUであるすべての $i$ について、棒 $i$ が倒れていないこと。
• $S$ の $i$ 番目の文字が.であるすべての $i$ について、棒 $i$ が「左に倒れている」、「右に倒れている」、「倒れていない」のいずれかであること。

$N$ 本の棒の倒し方のうち、正しいものの総数を $998244353$ で割った余りを求めてください。 ただし棒の倒し方は、棒 $i$ の状態(左に倒れている、右に倒れている、倒れていない)が異なるような $i$ が存在するとき、またそのときに限り異なるとみなされます。

入力

整数 $N$、文字列 $S$ が以下の形式で与えられます。

$N$
$S$

制約

• $N$ は $1$ 以上 $2 \times 10^5$ 以下の整数
• $S$ はL,R,U,.からなる $N$ 文字の文字列

出力

答えを出力し、最後に改行してください。

サンプル

サンプル1

入力サンプルをコピー

入力

3
..L

出力

5

棒の倒し方を文字列として表現したものを、「$N$ 文字の文字列であって、以下の条件をすべて満たすもの」と定めます。この方法において、ある棒の倒し方についてその文字列表現は一意に定まります。

• 棒 $i$ が左に倒れているとき、$i$ 番目の文字はLであること。
• 棒 $i$ が右に倒れているとき、$i$ 番目の文字はRであること。
• 棒 $i$ が倒れていないとき、$i$ 番目の文字はUであること。

下図におけるLLL,LUL,ULL,UUL,RULの $5$ 通りの棒の倒し方がすべての条件を満たすので、正しい棒の倒し方です。

また、下図のような棒の倒し方は条件を満たしません。

• URL: $1$ つ目の条件に違反します(棒 $2$ が右に倒れ、かつ棒 $3$ が左に倒れています)。
• LUU: $2$ つ目の条件に違反します(棒 $3$ が倒れていません)。
• RLR: $1$ つ目の条件に違反(棒 $1$ が右に倒れ、かつ棒 $2$ が左に倒れています)し、さらに $2$ つ目の条件に違反します(棒 $3$ が右に倒れています)。

6
..L..R

40

8
.RL..U..

0

30
.....R.....U...R..L.........L.

144875014