CF1608D Dominoes

给定 $n$ 个多米诺骨牌。每个骨牌有一个左格和一个右格。每个格子可以被涂成黑色或白色。有些格子已经被涂色，而有些还没有。 当且仅当存在一种重新排列骨牌的顺序，使得对于每个 $1 \le i \le n$，第 $i$ 个骨牌的右格颜色与第 $((i \bmod n)+1)$ 个骨牌的左格颜色不同，这种涂色方式被认为是合法的。 注意，你不能旋转骨牌，因此左格始终是左格，右格始终是右格。 请计算有多少种合法的方式来给尚未涂色的格子涂色。如果存在某个格子在两种方案中分别被涂成白色和黑色，则这两种方案被认为是不同的。特别地，涂色方案 BW WB 和 WB BW 被认为是不同的（且都不合法）。 由于答案可能非常大，请输出答案对 $998\,244\,353$ 取模后的结果。

输入的第一行包含一个整数 $n$（$1 \le n \le 10^5$）——多米诺骨牌的数量。 接下来的 $n$ 行描述每个骨牌。每行包含两个字符，分别表示左格和右格。字符 B 表示该格子为黑色，字符 W 表示该格子为白色，字符 ? 表示该格子尚未涂色。

输出一个整数，表示问题的答案。

在第一个测试用例中，只有一个骨牌，我们需要它的右格颜色与左格颜色不同。只有一种方式可以实现这一点。 在第二个测试用例中，只有 $2$ 种合法的涂色方式： BB WW 和 WB WB。 由 ChatGPT 4.1 翻译