给定一个圆，圆上有 $n$ 个不同的点，这些点将圆分成了 $n$ 条弧。你的任务是确定满足特定条件的有效染色方案的数量。圆上的每个点可以染成红色或蓝色，每条弧可以染成黄色或粉色。可以在颜色相同的点之间添加弦，限制条件是弦不能连接红色点和蓝色点。任意两条弦不能相交。此外，每个点最多只能连接一条弦。添加所有弦后，圆被这些弦分割成若干区域。

如果一种染色方案能够通过添加弦，使得分割后的每个区域都是单色的，则称该染色方案是“好的”（good）。如果一个区域不包含两种颜色的弧，则称该区域是单色的。你的目标是计算满足条件的“好的”染色方案数量，同时考虑某些点和弧的指定颜色。

给定某些点和弧的初始颜色，计算有效染色方案的数量，结果对 $998\,244\,353$ 取模。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 5 \cdot 10^4$)。第二行包含一个字符串 $s = s_1s_2 \dots s_{2n}$，表示弧和点的颜色类型。

对于每个奇数 $i$，字符 $s_i$ 只能是 “Y”、“P” 或 “?”，分别表示第 $\frac{i+1}{2}$ 条弧的颜色为黄色、粉色，或可以是两种颜色中的任意一种。 对于每个偶数 $i$，字符 $s_i$ 只能是 “R”、“B” 或 “?”，分别表示第 $\frac{i}{2}$ 个点的颜色为红色、蓝色，或可以是两种颜色中的任意一种。

输出格式

输出一行，包含一个整数：有效染色方案的数量，对 $998\,244\,353$ 取模。

样例

样例输入 1

2
????

样例输出 1

12

样例输入 2

3
??YR?B

样例输出 2

4

样例输入 3

5
YBYRPBYRYB

样例输出 3

0

说明

在样例 1 中，12 种有效的染色方案为：YBYB, YBYR, YRYB, YRYR, PBPB, PBPR, PRPB, PRPR, YBPB, YRPR, PBYB, PRYR。

在样例 2 中，以下图形有助于直观理解：

左图显示了染色前的圆；中间的图表示一种有效的染色方案 PBYRYB，我们可以将两个染成 B 的点用弦连接起来，证明该染色方案是好的；右图表示一种无效的染色方案 PBYRPB。