Problem Statement

$N$ people are sitting around a round table, and numbered $1$ to $N$ in a counterclockwise order. Each person has a dominant hand: left or right.

There are $N$ spoons numbered $1$ to $N$ on the round table, with one spoon placed between each pair of adjacent people. For each $1 \leq i \leq N$, to the left and right of person $i$, there are spoons $i$ and $(i+1)$, respectively. Here, spoon $(N+1)$ refers to spoon $1$.

Below is a diagram for $N = 4$.

You are given a permutation $(P_1, \dots, P_N)$ of $(1, \dots, N)$. In the order $i=1,\dots,N$, person $P_i$ will act as follows:

• If there is a spoon remaining on left or right side, they will take one of them.
• If there are spoons remaining on both sides, they will take the spoon on the side of their dominant hand.
• Otherwise, they do nothing.

You are also given a string $S$ of length $N$ consisting of L, R, and ?. Among the $2^N$ possible combinations of dominant hands, find how many satisfy all of the following conditions, modulo $998244353$:

• If the $i$-th character of $S$ is L, person $i$ is left-handed.
• If the $i$-th character of $S$ is R, person $i$ is right-handed.
• When everyone has finished acting, everyone has taken a spoon.

Constraints

• All input values are integers.
• $2 \leq N \leq 2 \times 10^5$
• $(P_1, \dots, P_N)$ is a permutation of $(1, \dots, N)$.
• $S$ is a string of length $N$ consisting of L, R, and ?.

Input

The input is given from Standard Input in the following format:

N
P_1 \dots P_N
S

Output

Print the answer in a single line.