Go

题目描述

围棋是一种对抗游戏，目标是用己方棋子围住比对手更大的棋盘区域。围棋中的核心概念之一是“气”：与棋子所在连通块相邻、且没有棋子的交叉点。

若一枚黑棋或白棋在上、下、左、右四个方向上至少相邻一个气，或者它与同色的一枚活棋处于同一个连通块中，则称这枚棋子是活的。两个同色棋子若在上下或左右方向相邻，则称它们直接相连；若同色棋子 $s_1$ 与 $s_k$ 之间存在棋子序列 $s_1,s_2,\ldots,s_k$，使得相邻两枚棋子均同色且直接相连，则称它们位于同一个连通块中。

下图左侧的两枚白棋都没有气，被周围的黑棋提掉；右侧最右边的白棋同样不是活棋，即使最左边的黑棋也不是活棋。两幅图中未存活白棋的数量分别为 $2$ 和 $1$。

给定一个由 $n$ 条横线和 $n$ 条竖线组成的棋盘，部分交叉点上放有棋子。现在需要分别翻转每一枚棋子的颜色（黑变白、白变黑），并求出翻转后没有存活的白棋数量。

每次翻转都是独立的：翻转下一枚棋子之前，其他棋子都恢复为初始颜色。棋盘大小不一定是 $19\times 19$，黑白棋子的数量也没有现实棋局中的限制。

将初始棋盘上的所有棋子按行号从上到下为第一关键字、列号从左到右为第二关键字排序。设棋子总数为 $m$，翻转排序后第 $i$ 枚棋子时，没有存活的白棋数量为 $a_i$。定义

请输出 $E$ 对 $10^9+7$ 取模后的结果。注意，式中的底数 $10^6+7$ 与模数 $10^9+7$ 不同。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据，第一行包含一个整数 $n$（$2\le n\le 10^3$），表示棋盘的边长。

接下来 $n$ 行，第 $i$ 行包含一个长度为 $n$ 的字符串。其中字符 x（ASCII 码 $120$）表示黑棋，字符 o（ASCII 码 $111$）表示白棋，字符 .（ASCII 码 $46$）表示空交叉点。

保证所有测试数据的 $n$ 之和不超过 $5\times 10^3$。

输出格式

对于每组测试数据，输出一行一个整数，表示编码后的答案 $E$ 对 $10^9+7$ 取模的结果。

样例输入 1

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

样例输出 1

0
870527216
485539347

样例解释

对于第二组测试数据，按 $(1,2),(2,1),(2,2),(2,3),(3,1),(3,2)$ 的顺序依次翻转棋子时，没有存活的白棋数量分别为 $1,0,1,2,0,0$。

对于第三组测试数据，棋盘上的所有棋子（无论黑白）都不是活棋。

数据范围

• $1\le T\le 2500$。
• $2\le n\le 10^3$。
• 所有测试数据的 $n$ 之和不超过 $5\times 10^3$。