Dominoes

题意翻译

有 $n$ 个多米诺骨牌，每个骨牌由左右两个方格组成。有的方格已经被涂上了白色（``W``）或者黑色（``B``），剩下的方格（``?``）还没有被涂色。你需要给所有未涂色的方格涂上黑色或者白色。 一种涂色方案被认为是合法的，当且仅当存在一种排列骨牌方案使得任意两个相邻的骨牌相邻方格的颜色不同。特殊地，第一格骨牌的左端和最后一个骨牌的右端被认为是相邻的。值得注意的是不能旋转它们，也就是不能交换左右方格的颜色。 两种涂色方案被认为是不同的，当且仅当存在一个方格在一个方案中被涂白在另一个方案中被涂黑。形如 ``BW WB`` 和 ``WB BW`` 的两个方案被认为是不同的方案。（同时他们都是非法的）。 求方案数对 $998244353$ 取模的结果。 by [Error_Eric](/user/217300).

题目描述

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 $ .

输入输出格式

输入格式

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.

输出格式

Print a single integer — the answer to the problem.

输入输出样例

输入样例 #1

1
?W

输出样例 #1

1

输入样例 #2

2
??
W?

输出样例 #2

2

输入样例 #3

4
BB
??
W?
??

输出样例 #3

10

说明

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.

题意翻译

有 $n$ 个多米诺骨牌，每个骨牌由左右两个方格组成。有的方格已经被涂上了白色（``W``）或者黑色（``B``），剩下的方格（``?``）还没有被涂色。你需要给所有未涂色的方格涂上黑色或者白色。 一种涂色方案被认为是合法的，当且仅当存在一种排列骨牌方案使得任意两个相邻的骨牌相邻方格的颜色不同。特殊地，第一格骨牌的左端和最后一个骨牌的右端被认为是相邻的。值得注意的是不能旋转它们，也就是不能交换左右方格的颜色。 两种涂色方案被认为是不同的，当且仅当存在一个方格在一个方案中被涂白在另一个方案中被涂黑。形如 ``BW WB`` 和 ``WB BW`` 的两个方案被认为是不同的方案。（同时他们都是非法的）。 求方案数对 $998244353$ 取模的结果。 by [Error_Eric](/user/217300).