分数: 400 点
问题陈述
N 人们围坐在圆桌旁,并编号 1 to N 按逆时针顺序。每个人都有一只惯用手:左手或右手。
有 N 勺子编号 1 to N 在圆桌上,每对相邻的人之间放一个勺子。对于每个 1 \leq i \leq N,在人的左侧和右侧 i,有勺子 分别是 i 和 (i+1)。在这里,勺子 (N+1) 指勺子 1.
下图是 N = 4.

给你一个排列 (P_1, \dots, P_N) of (1, \dots, N)。按顺序 i=1,\dots,N, 人 P_i 将执行以下操作:
- 如果左边或右边还有一把勺子,他们就会拿其中一个。
- 如果两边都剩下勺子,他们会拿惯用手一侧的勺子。
- 否则,他们什么也不做。
还给你一个字符串 S 长度 N 组成 L, R,和 ?。其中 2^N 优势手的可能组合,找出有多少满足以下所有条件,取模 998244353:
- 如果 i- 第一个字符 S is
L, 人 i 是左撇子。 - 如果 i- 第一个字符 S is
R, 人 i 是右撇子。 - 大家演完了,大家都拿了勺子。
约束
- 所有输入值均为整数。
- 2 \leq N \leq 2 \times 10^5
- (P_1, \dots, P_N) 是一个排列 (1, \dots, N).
- S 是一个长度为 N 组成
L,R,和?.
输入
输入由标准输入按以下格式给出:
N P_1 \dots P_N S
输出
在一行中打印答案。
示例输入 1
3 1 2 3 L??
示例输出 1
2
当人 1, 2,和 3 分别为左撇子、左撇子、右撇子,执行的动作如下:
- 人 1 开始行动。两边都有勺子,所以人 1 拿勺子 1 在左侧,与他们的惯用手相同。
- 人 2 开始行动。两边都有勺子,所以人 2 拿勺子 2 在左侧,与他们的惯用手相同。
- 人 3 开始行动。右边没有勺子,但是有勺子 3 留在左侧,所以他们拿了勺子 3。大家演完了,拿勺子。
这种优势牌组合满足条件。此外,当人 1, 2, 3 都是左撇子。
示例输入 2
3 1 3 2 R?L
示例输出 2
0
没有优势手的组合满足条件。
示例输入 3
12 6 2 9 3 1 4 11 5 12 10 7 8 ????????????
示例输出 3
160