Score: $400$ points

问题陈述

$N$ 个人围坐在一张圆桌旁，按逆时针顺序编号为 $1$ 至 $N$。每个人都有一个主导手：左手或右手。

圆桌上有 $N$ 把勺子，编号为 $1$ 至 $N$，每两个人之间放置一把勺子。对于每个 $1 \leq i \leq N$，人 $i$ 的左边和右边分别有勺子 $i$ 和 $(i+1)$。这里，勺子 $(N+1)$ 指的是勺子 $1$。

下面是 $N = 4$ 时的示意图。

你将得到一个排列 $(P_1, \dots, P_N)$，它是由 $(1, \dots, N)$ 组成的。按照顺序 $i=1,\dots,N$，人 $P_i$ 将执行以下操作：

• 如果左边或右边还有勺子，他们将拿走其中一把。
  • 如果两边都还有勺子，他们将拿走他们主导手那边的勺子。
• 否则，他们将不做任何操作。

你还得到了一个长度为 $N$ 的字符串 $S$，由 L、R 和 ? 组成。在 $2^N$ 种可能的主导手组合中，找出满足以下所有条件的数量，对 $998244353$ 取模：

• 如果 $S$ 中的第 $i$ 个字符是 L，则人 $i$ 是左撇子。
• 如果 $S$ 中的第 $i$ 个字符是 R，则人 $i$ 是右撇子。
• 当每个人都完成操作后，每个人都拿到了一把勺子。

以上为大语言模型 kimi 翻译，仅供参考。

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.

Sample Input 1

3
1 2 3
L??

Sample Output 1

2

When persons $1$, $2$, and $3$ are left-handed, left-handed, and right-handed, respectively, the actions are performed as follows:

• Person $1$ starts acting. There are spoons on both sides, so person $1$ takes spoon $1$ on the left side, which is the same as their dominant hand.
• Person $2$ starts acting. There are spoons on both sides, so person $2$ takes spoon $2$ on the left side, which is the same as their dominant hand.
• Person $3$ starts acting. There is no spoon on the right side, but spoon $3$ is remaining on the left side, so they take spoon $3$. Everyone has finished acting and taken a spoon.

This combination of dominant hands satisfies the conditions. Besides, the conditions are also satisfied when persons $1, 2, 3$ are all left-handed.

Sample Input 2

3
1 3 2
R?L

Sample Output 2

0

No combinations of dominant hands satisfy the conditions.

Sample Input 3

12
6 2 9 3 1 4 11 5 12 10 7 8
????????????

Sample Output 3

160