取勺问题

时间限制：2s
空间限制：1024MB

题目描述

$N$ 个人按逆时针方向编号为 $1$ 到 $N$，围坐在圆桌旁。相邻两人之间各有一把勺子，共有 $N$ 把：人 $i$ 左侧是勺子 $i$，右侧是勺子 $(i+1)$，其中勺子 $(N+1)$ 表示勺子 $1$。

给定排列 $P$，人们依次按 $P_1,P_2,\ldots,P_N$ 行动。如果左右至少有一把勺子剩余，就取走一把；若两把都在，则取惯用手一侧的勺子；若两把都不在，则什么也不做。

字符串 $S$ 描述惯用手限制：L 表示必须左利手，R 表示必须右利手，? 表示任选。求满足限制且最终每个人都拿到一把勺子的惯用手组合数，对 $998244353$ 取模。

输入格式

N
P_1 P_2 ... P_N
S

输出格式

输出满足条件的组合数对 $998244353$ 取模的结果。

样例输入 1

3
1 2 3
L??

样例输出 1

2

数据范围

• $2\le N\le2\times10^5$；
• $P$ 是 $1$ 到 $N$ 的一个排列；
• $S$ 是由 L、R、? 组成的长度为 $N$ 的字符串。