#P18407. Bocchi the Rock

Bocchi the Rock

Bocchi the Rock

圆周上有 nn 个不同的点,它们把圆周分成 nn 条弧。每个点可以染成红色或蓝色,每条弧可以染成黄色或粉色。

你可以在同色的两个点之间添加弦,不能连接一红一蓝的两个点。任意两条弦不能相交,且每个点至多连接一条弦。添加这些弦后,圆内部被划分为若干区域。

若可以添加一些满足要求的弦,使得到的每个区域都为单色,则称该着色为好着色。这里,区域“单色”是指它不同时包含黄色弧和粉色弧,只比较其圆周弧的颜色。

有些点和弧的颜色已经指定。求符合这些指定颜色的好着色数量,答案对 998244353998244353 取模。数的是颜色的补全方式,不是添加弦的方式;同一着色有多种合法连弦方法时只计一次。输入位置区分各点和弧。

输入格式

第一行包含整数 nn,满足 2≤n≤5⋅1042\le n\le5\cdot10^4。

第二行包含长度为 2n2n 的字符串 s=s1s2…s2ns=s_1s_2\ldots s_{2n},沿圆周按弧、点、弧、点的顺序记录颜色:

  • 对奇数 ii,sis_i 只可能为 Y、P、?,表示第 (i+1)/2(i+1)/2 条弧是黄色、粉色,或者颜色尚未确定。
  • 对偶数 ii,sis_i 只可能为 R、B、?,表示第 i/2i/2 个点是红色、蓝色,或者颜色尚未确定。

首尾相接:最后一个点之后是第一条弧。? 只能在该位置允许的两种颜色中选择。

输出格式

输出一行一个整数,表示符合已知颜色约束的好着色数量,对 998244353998244353 取模后的值。

样例 1

2
????
12

样例 2

3
??YR?B
4

样例 3

5
YBYRPBYRYB
0

样例说明

样例 1 的十二种好着色分别为:YBYB、YBYR、YRYB、YRYR、PBPB、PBPR、PRPB、PRPR、YBPB、YRPR、PBYB、PRYR。

下图为样例 2 的原题示意图。左图是颜色尚未补全时的圆;中图的 PBYRYB 是好着色,可以连接两个蓝点得到单色区域;右图的 PBYRPB 不是好着色。

样例2原题三个圆与弦示意图