P9628 [ICPC 2020 Nanjing R] Go

**围棋**是一种对抗性游戏，目的是用自己的石头比对手的石头包围更大的棋盘总面积。游戏的核心理念是**自由**，即一个开放点，或者更确切地说，是棋盘上垂直线和水平线的交叉点，上面没有石头，与群体接壤。 一个白色或黑色的石头，如果它至少有一个直接正交相邻的自由（上、下、左或右），或者必须与一块有生命的相同颜色的石头在同一个连接组中，那么它是有生命的，被称为**活着**。我们说，如果两块颜色相同的石头正交相邻，它们就直接相连。如果存在一系列石头 $s_1,s_2,…,s_k$ ，对于所有 $1\leq i

有多个测试样例。输入的第一行包含一个整数 $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$ 。 对于第三个测试样例，棋盘上的所有石头，无论是黑色还是白色，都不是活着的。