[ICPC2020 Nanjing R] Go

### 题目描述 **围棋**是一种对抗性游戏，目的是用自己的石头比对手的石头包围更大的棋盘总面积。游戏的核心理念是**自由**，即一个开放点，或者更确切地说，是棋盘上垂直线和水平线的交叉点，上面没有石头，与群体接壤。 一个白色或黑色的石头，如果它至少有一个直接正交相邻的自由（上、下、左或右），或者必须与一块有生命的相同颜色的石头在同一个连接组中，那么它是有生命的，被称为**活着**。我们说，如果两块颜色相同的石头正交相邻，它们就直接相连。如果存在一系列石头 $s_1,s_2,…,s_k$ ，对于所有 $1\leq i<k$ ， $s_{i-1}$ 和 $s_i$ 颜色相同且正交相邻，则相同颜色的两块石头 $s_1$ 和 $s_k$ 属于同一连通组。 例如，在下图的左侧，两块白色的石头都没有活着，因为它们被周围的黑色石头捕获了；而在右边的部分，最右边的白色石头也没有生命，即使最左边的黑色石头也没有。  给定一个有 $n$ 条垂直线和 $n$ 条水平线的棋盘，其中可能有一些石头躺在上面，请计算黑色石头捕获的白色石头的数量（也就是说，计算没有生命的白色石头数量）。上述例子的结果分别为 $2$ 和 $1$ 。 然而，我们亲爱的朋友 Kotori 认为这个问题让我们聪明的参赛者解决太简单了，所以她想让你独立翻转每块石头的颜色（也就是说，把黑色的石头变成白色的石头，反之亦然$^1$），并在每次翻转后找到相应的答案。 独立翻转的意思是，在翻转石头的颜色之前，其他石头应该变回原来的颜色。还要注意，这个问题中的数据不是来自真实世界，这意味着棋盘的大小不一定是 $19×19$ ，黑白石头的数量可以是任意整数。 $^1$反之亦然：在这里，它可以用 ```把白色的石头变成黑色的石头``` 来代替。这是现代英语中非常常见的短语，尤其是在学术写作中，所以请记住。 ### 输入格式 有多个测试样例。输入的第一行包含一个整数 $T$ 表示测试样例的数量。对于每个测试样例： 第一行包含一个整数 $n$ ($2\leq n\leq 10^3$)，表示棋盘的边长。 对于接下来 $n$ 行，第 $i$ 行包含一个字符串 $s_{i,1},s_{i,2},…,s_{i,n}$ 。其中 $s_{i,j}=‘x’$ 表示第 $i$ 行第 $j$ 列有一个黑石头，$s_{i,j}=‘o’$ 表示第 $i$ 行第 $j$ 列有一个白石头，$s_{i,j}=‘.’$ 表示第 $i$ 行第 $j$ 列是空的。 保证所有测试样例的 $n$ 之和不超过 $5×10^3$ 。 ### 输出格式 对于每个测试用例输出一个整数 $E\bmod10^9+7$ 作为如下编码的答案： - 对所有石头进行排序，以其行号（从上到下）为第一关键字，以其列号（从左到右）为第二关键字； - $E=\sum\limits_{i=1}^m(10^6+7)^{m-i}a_i$ ，其中 $m$ 是石头的数量， $a_i$ 是翻转第 $i$ 次颜色后没有生命的白色石头的数量。 $\underline{\textbf{注意}\text{：\textsf{模数}和\textsf{基数}是}\textbf{不同}{的}}$ 。（我们恳求你注意这句话。如果这不是 pdf 文件，我宁愿它像疯了一样闪烁。） ### 说明/提示 对于第二个测试样例，按照 $(1,2),(2,1),(2,2),(2,3),(3,1),(3,2)$ 的顺序翻转石头后，死亡的白色石头数量分别为 $1,0,1,2,0,0$ 。 对于第三个测试样例，棋盘上的所有石头，无论是黑色还是白色，都不是活着的。

$\textit{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 $\textit{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 $\textit{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 $s_1$ and $s_k$ of the same color are in the same connected group if there exists a sequence of stones $s_1, s_2,\cdots, s_k$ such that for all $1 \le i < k$, $s_{i-1}$ and $s_i$ 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 $n$ vertical and $n$ 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 $2$ and $1$, 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 versa$^1$) 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 $19 \times 19$, and the number of white and black stones can be any integer. $^1$ Vice 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 integer $T$ indicating the number of test cases. For each test case: The first line contains one integer $n$ ($2\le n \le 10^3$) indicating the length of the board side. For the next $n$ lines, the $i$-th line contains a string $s_{i,1},s_{i,2},\cdots,s_{i,n}$ ($s_{i,j}$ $\in$ $\{\text{`x' (ascii: 120)}$, $\text{`o' (ascii: 111)}$, $\text{`.' (ascii: 46)}\}$), where $s_{i,j} = \text{`x'}$ indicates that the intersection on the $i$-th row and the $j$-th column contains a black stone. Similarly $s_{i, j} = \text{`o'}$ for a white stone and $s_{i,j} = \text{`.'}$ for an empty intersection. It's guaranteed that the sum of $n$ over all test cases does not exceed $5 \times 10^3$.

For each test case output an integer $E$ modulo $(10^9 + 7)$ which is the answer encoded as follows: - 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; - $E=\sum \limits_{i=1}^m (10^6 + 7)^{m-i}a_i$, where $m$ is the number of stones and $a_i$ is the number of white stones not alive after flipping the color of the $i$-th stone. $\underline{\text{NOTE that the MODULUS and the BASE are} \textbf{ DIFFERENT}}$. (We're begging you to notice this sentence. If this is not a pdf file I would rather it flashes and twinkles like crazy.)

3
2
.o
..
3
.x.
xoo
ox.
2
oo
oo

0
870527216
485539347

For the second sample test case, after flipping the stones in the order of $(1,2)$, $(2,1)$, $(2,2)$, $(2,3)$, $(3,1)$, $(3,2)$, the number of dead white stones are $1$, $0$, $1$, $2$, $0$, $0$, repectively. For the third sample test case all stones on the chessboard, black or white, are not alive.