Problem Statement

There are $N$ sticks arranged in a horizontal row. The sticks are numbered $1, 2, \dots, N$ from left to right, and the stick numbered with an integer $i$ is called "stick $i$". You are given a positive integer $N$ and a string $S$ of $N$ characters consisting of L,R,U,.. You can put each of the $N$ sticks arranged in a straight line into one of the following states: "knocked down to the left", "knocked down to the right", or "not knocked down".

A way of knocking down the $N$ sticks is called correct if it satisfies all of the following conditions. In the text below, $i$ is an integer satisfying $1 \le i \le N$.

• There is no stick that has fallen to the right whose right neighbor has fallen to the left. (More strictly, there must not exist an integer $k$ satisfying $1 \le k \le N-1$ such that stick $k$ has fallen to the right and stick $k+1$ has fallen to the left.)
• For every $i$ such that the $i$-th character of $S$ is L, stick $i$ has fallen to the left.
• For every $i$ such that the $i$-th character of $S$ is R, stick $i$ has fallen to the right.
• For every $i$ such that the $i$-th character of $S$ is U, stick $i$ has not fallen.
• For every $i$ such that the $i$-th character of $S$ is ., stick $i$ is in one of the states "fallen to the left", "fallen to the right", or "not fallen".

Find the total number of correct ways of knocking down the $N$ sticks, modulo $998244353$. Two ways of knocking down the sticks are considered different if and only if there exists an $i$ such that the state of stick $i$ (fallen to the left, fallen to the right, or not fallen) differs.

Input

An integer $N$ and a string $S$ are given in the following format.

$N$
$S$

Constraints

• $N$ is an integer between $1$ and $2 \times 10^5$, inclusive.
• $S$ is a string of $N$ characters consisting of L,R,U,..

Output

Print the answer, followed by a newline.

Sample

Sample 1

Input

3
..L

Output

5

We define the string representation of a way of knocking down the sticks as "the string of $N$ characters satisfying all of the following conditions". With this method, the string representation of a given way of knocking down the sticks is uniquely determined.

• If stick $i$ has fallen to the left, the $i$-th character is L.
• If stick $i$ has fallen to the right, the $i$-th character is R.
• If stick $i$ has not fallen, the $i$-th character is U.

The $5$ ways of knocking down the sticks in the figure below, LLL,LUL,ULL,UUL,RUL, satisfy all of the conditions, so they are correct ways of knocking down the sticks.

On the other hand, the ways of knocking down the sticks shown in the figure below do not satisfy the conditions.

• URL: It violates the $1$st condition (stick $2$ has fallen to the right and stick $3$ has fallen to the left).
• LUU: It violates the $2$nd condition (stick $3$ has not fallen).
• RLR: It violates the $1$st condition (stick $1$ has fallen to the right and stick $2$ has fallen to the left), and also violates the $2$nd condition (stick $3$ has fallen to the right).

6
..L..R

40

8
.RL..U..

0

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

144875014