题目描述

有 $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$ 取模。

样例 1

输入

3
1 2 3
L??

输出

2

样例 2

输入

3
1 3 2
R?L

输出

0

样例 3

输入

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

输出

160

说明/提示

限制

• 输入的所有数值均为整数。
• $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 翻译