NC216007. Go
描述
Go is an adversarial game with the objective of surrounding a larger total area of the board with one's stones than the opponent's. The core idea of the game is the concept of liberty, which is an open point, or rather, an intersection of vertical and horizontal lines on the chessboard with no stones on it, bordering the group.
A stone, white or black, is called alive if it has at least one liberty directly orthogonally adjacent (up, down, left, or right), or must be in the same connected group with a stone of the same color which is alive. We say two stones of the same color are directly connected if they're orthogonally adjacent. We say two stones
and 
of the same color are in the same connected group if there exists a sequence of stones 
such that for all 
, 
and 
are of the same color and are directly connected.
For example, in the left part of the below figure, neither of the two white stones is alive, as they're captured by the surrounding black stones; While in the right part, the rightmost white stone is also not alive, even if the leftmost black stone is also not alive.
Given a chessboard with 
vertical and horizontal lines where some stones might be lying on, please calculate the number of white stones captured by the black ones (that is to say, calcaulate the number of white stones not alive). The results for the above examples are 
and 
, respectively.
However, our dear friend Kotori thinks that this problem is too simple for our clever contestants to solve, so she would like to heat things up by instead asking you to flip the color of each stone (that is to say, change a black stone to a white one, or vice versa2) independently and find out the corresponding answer after each flip.
A stone, white or black, is called alive if it has at least one liberty directly orthogonally adjacent (up, down, left, or right), or must be in the same connected group with a stone of the same color which is alive. We say two stones of the same color are directly connected if they're orthogonally adjacent. We say two stones
For example, in the left part of the below figure, neither of the two white stones is alive, as they're captured by the surrounding black stones; While in the right part, the rightmost white stone is also not alive, even if the leftmost black stone is also not alive.
However, our dear friend Kotori thinks that this problem is too simple for our clever contestants to solve, so she would like to heat things up by instead asking you to flip the color of each stone (that is to say, change a black stone to a white one, or vice versa2) independently and find out the corresponding answer after each flip.
By flipping independently we mean that before flipping the color of a stone, the other stones should change back to their original color. Also note that the data in this problem is not from the real world, which means that the size of the chessboard is not necesssarily 
, and the number of white and black stones can be any integer.
2Vice versa: The reverse is also true. Here it can be replaced with "change a white stone to a black one". This is a very common phrase in modern English especially in academic writing, so please bear it in mind.
输入描述
There are multiple test cases. The first line of the input contains an integerindicating the number of test cases. For each test case:
The first line contains one integer) indicating the length of the board side.
For the next-th line contains a string
(
,
,
), where
indicates that the intersection on the
-th column contains a black stone. Similarly
for a white stone and
for an empty intersection.
It's guaranteed that the sum of.
输出描述
For each test case output an integermodulo
which is the answer encoded as follows:
1. Sort all the stones with their row number (from top to bottom) as the primary sort key and their column number (from left to right) as the secondary sort key;2., where
is the number of stones and
is the number of white stones not alive after flipping the color of the
NOTE that the MODULUS and the BASE are DIFFERENT.
示例1
输入:
3 2 .o .. 3 .x. xoo ox. 2 oo oo
输出:
0 870527216 485539347