CF1608D.Dominoes

You are given $n$ dominoes. Each domino has a left and a right cell. Each cell can be colored either black or white. Some cells are already colored, while some aren't yet.

The coloring is said to be valid if and only if it is possible to rearrange the dominoes in some order such that for each $1 \le i \le n$ the color of the right cell of the $i$-th domino is different from the color of the left cell of the $((i \bmod n)+1)$-st domino.

Note that you can't rotate the dominoes, so the left cell always remains the left cell, and the right cell always remains the right cell.

Count the number of valid ways to color the yet uncolored cells of dominoes. Two ways are considered different if there is a cell that is colored white in one way and black in the other. In particular, colorings BW WB and WB BW different (and both invalid).

As this number can be very big, output it modulo $998\,244\,353$.

给你 $n$ 个骨牌。每个骨牌有一个左单元格和一个右单元格。每个单元格可以被染成黑色或白色。部分单元格已被染色，而其余单元格尚未染色。

当且仅当能够将这些骨牌以某种顺序重新排列，使得对每个 $1 \le i \le n$，第 $i$ 个骨牌的右单元格颜色与第 $((i \bmod n)+1)$ 个骨牌的左单元格颜色不同时，该染色方案被称为合法的。

注意：你不能旋转骨牌，因此左单元格始终为左单元格，右单元格始终为右单元格。

请你计算将所有尚未染色的单元格进行染色，使得最终染色方案合法的方案总数。若两种方案存在某个单元格在一种方案中染为白色、而在另一种方案中染为黑色，则认为它们是不同的方案。特别地，染色方案 BW WB 与 WB BW 被视为不同（且二者均不合法）。

由于答案可能非常大，请输出其对 $998\,244\,353$ 取模的结果。

The first line of the input contains a single integer $n$ ($1 \le n \le 10^5$) — the number of dominoes.

The next $n$ lines describe dominoes. Each line contains two characters which represent the left and the right cell. Character B means that the corresponding cell is black, character W means that the corresponding cell is white, and ? means that the cell is yet to be colored.

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

接下来的 $n$ 行描述了这些多米诺骨牌。每行包含两个字符，分别表示该骨牌的左格和右格。字符 B 表示对应格子为黑色，字符 W 表示对应格子为白色，字符 ? 表示该格子尚未着色。

Print a single integer — the answer to the problem.

输出一个整数——该问题的答案。

In the first test case, there is only one domino, and we need the color of its right cell to be different from the color of its left cell. There is only one way to achieve this.

In the second test case, there are only $2$ such colorings:

BB WW and WB WB.

在第一个测试用例中，只有一张多米诺骨牌，我们需要其右方格的颜色与左方格的颜色不同。仅有一种方式可以实现这一点。

在第二个测试用例中，仅有 $2$ 种满足条件的染色方案：

BB WW 和 WB WB。