← 返回题目列表

Codeforces · 1608/D

D. 多米诺骨牌

中文机器翻译题面 查看原题

你得到了 $$$n$$$ 多米诺骨牌。每个多米诺骨牌都有一个左单元和一个右单元。每个单元格可以涂成黑色或白色。有些细胞已经着色,而有些还没有。

当且仅当可以按某种顺序重新排列多米诺骨牌时,着色才被认为是有效的,使得对于每个 $$$1 \le i \le n$$$,第 $$$i$$$ 多米诺骨牌的右侧单元格的颜色与第 $$$((i \bmod n)+1)$$$-st 多米诺骨牌的左侧单元格的颜色不同。

请注意,您无法旋转多米诺骨牌,因此左侧单元格始终保持左侧单元格,右侧单元格始终保持右侧单元格。

计算为多米诺骨牌上尚未着色的单元格着色的有效方法的数量。如果有一个单元格以一种方式着色为白色而以另一种方式着色为黑色,则两种方式被认为是不同的。特别是,着色 BW WB 和 WB BW 不同(且均无效)。

由于这个数字可能非常大,因此输出它对 $$$998\,244\,353$$$ 取模。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 多米诺骨牌的数量。

接下来的 $$$n$$$ 行描述多米诺骨牌。每行包含两个字符,分别代表左侧和右侧单元格。字符 B 表示对应的单元格为黑色,字符 W 表示对应的单元格为白色,?意味着细胞尚未着色。

输出

打印一个整数——问题的答案。

示例

输入 #1

1
?W

输出 #1

1

输入 #2

2
??
W?

输出 #2

2

输入 #3

4
BB
??
W?
??

输出 #3

10

注意

在第一个测试用例中,只有一个多米诺骨牌,我们需要其右侧单元格的颜色与其左侧单元格的颜色不同。只有一种方法可以实现这一目标。

在第二个测试用例中,只有 $$$2$$$ 这样的颜色:

BB WW 和 WB WB。