AT_arc175_a [ARC175A] Spoon Taking Problem

有 $N$ 个人围坐在圆桌旁，每个人按逆时针方向依次编号为 $1,\ 2,\ \ldots,\ N$。每个人都有一只惯用手，可能是左手或右手。 圆桌上有 $N$ 把编号为 $1,\ 2,\ \ldots,\ N$ 的勺子，每两个人之间放有一把勺子。对于每个 $1 \leq i \leq N$，第 $i$ 个人的左侧有勺子 $i$，右侧有勺子 $(i+1)$。这里，勺子 $(N+1)$ 指的是勺子 $1$。 下图展示了 $N=4$ 时的示意图。  给定一个 $(1,\ \dots,\ N)$ 的排列 $(P_1,\ \dots,\ P_N)$。按照 $i=1,\dots,N$ 的顺序，第 $P_i$ 个人依次进行如下操作： - 如果自己左侧或右侧还有勺子，则从中取走一把。 - 如果自己两侧的勺子都还在，则取走与自己惯用手相同侧的勺子。 - 否则什么也不做。 给定一个由 `L`、`R`、`?` 组成的长度为 $N$ 的字符串 $S$。$N$ 个人的惯用手组合共有 $2^N$ 种可能，请你计算其中满足以下所有条件的组合数，并对 $998244353$ 取模： - 如果 $S$ 的第 $i$ 个字符为 `L`，则第 $i$ 个人必须是左撇子。 - 如果 $S$ 的第 $i$ 个字符为 `R`，则第 $i$ 个人必须是右撇子。 - 所有人操作结束后，每个人都拿到了一把勺子。

输入通过标准输入给出，格式如下： > $N\ P_1\ P_2\ \dots\ P_N\ S$

输出一个整数，表示满足条件的惯用手组合数，对 $998244353$ 取模。

## 限制 - 输入的所有数值均为整数。 - $2 \leq N \leq 2 \times 10^5$ - $(P_1,\dots,P_N)$ 是 $(1,\dots,N)$ 的一个排列。 - $S$ 是由 `L`、`R`、`?` 组成的长度为 $N$ 的字符串。 ## 样例解释 1 当第 $1,2,3$ 个人分别为左撇子、左撇子、右撇子时，操作如下： - 第 $1$ 个人开始操作。两侧的勺子都还在，因此取走左侧（与惯用手相同侧）的勺子 $1$。 - 第 $2$ 个人开始操作。两侧的勺子都还在，因此取走左侧的勺子 $2$。 - 第 $3$ 个人开始操作。右侧的勺子已经没有了，左侧的勺子 $3$ 还在，因此取走勺子 $3$。 所有人操作结束后，每个人都拿到了一把勺子。这个惯用手组合是满足条件的。除此之外，第 $1,2,3$ 个人都为左撇子的组合也满足条件。 ## 样例解释 2 不存在满足条件的惯用手组合。 由 ChatGPT 4.1 翻译