围棋是一种对抗性游戏，目标是通过棋子围住比对手更多的棋盘区域。游戏的核心概念是“气”，即棋子所在棋组周围的空点（棋盘上横竖线交叉且没有棋子的位置）。

如果一颗棋子（白子或黑子）至少有一口气（直接在上下左右相邻的位置），或者它与另一颗同色的存活棋子处于同一个连通块中，则称该棋子是“存活”的。如果两颗同色棋子在正交方向上相邻，则称它们直接相连。如果存在一个棋子序列 $s_1, s_2, \dots, s_k$，使得对于所有 $1 \le i < k$，$s_{i-1}$ 和 $s_i$ 同色且直接相连，则称两颗同色棋子 $s_1$ 和 $s_k$ 处于同一个连通块中。

例如，在下图中，左侧的两颗白子都不存活，因为它们被周围的黑子捕获；而在右侧，最右边的白子也不存活，即使最左边的黑子也不存活。

给定一个 $n \times n$ 的棋盘，上面可能放置了一些棋子，请计算被黑子捕获的白子数量（即计算不存活的白子数量）。上述示例的结果分别为 2 和 1。

然而，我们的好朋友 Kotori 认为这个问题对聪明的参赛者来说太简单了，所以她想增加难度：要求你独立地翻转每一颗棋子的颜色（即将黑子变为白子，或反之），并求出每次翻转后对应的答案。

“独立翻转”意味着在翻转某颗棋子的颜色之前，其他棋子应恢复到它们的原始颜色。此外，请注意本题中的数据并非来自现实世界，这意味着棋盘大小不一定是 $19 \times 19$，且白子和黑子的数量可以是任意整数。

输入格式

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

第一行包含一个整数 $n$ ($2 \le n \le 10^3$)，表示棋盘边长。

接下来的 $n$ 行，第 $i$ 行包含一个字符串 $s_{i,1}, s_{i,2}, \dots, s_{i,n}$ ($s_{i,j} \in \{'x', 'o', '.'\}$)，其中 $s_{i,j} = 'x'$ 表示第 $i$ 行第 $j$ 列的交叉点上有一颗黑子，$s_{i,j} = 'o'$ 表示白子，$s_{i,j} = '.'$ 表示空交叉点。

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

输出格式

对于每组测试数据，输出一个整数 $E$ 对 $(10^9 + 7)$ 取模的结果，该答案编码如下：

• 将所有棋子按行号（从上到下）作为第一关键字、列号（从左到右）作为第二关键字进行排序；
• $E = \sum_{i=1}^{m} (10^6 + 7)^{m-i} a_i$，其中 $m$ 是棋子总数，$a_i$ 是翻转第 $i$ 颗棋子的颜色后，不存活的白子数量。

注意：模数（$10^9 + 7$）和基数（$10^6 + 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$。

对于第三个样例测试数据，棋盘上所有的棋子（无论黑白）均不存活。