对于一个已知的序列，统计具有某种显著性质的子序列可以在一定程度上刻画该序列本身。

现在，Rikka 有一个长度为 $n$ 的序列 $A$，其元素记为 $a_1, a_2, \dots, a_n$，均为 $[1, n]$ 范围内的正整数。桥接关系矩阵（BRM）是一个元素取自 $\{0, 1\}$ 的 $n \times n$ 逻辑矩阵。在此，Rikka 基于给定的 BRM $M = (M_{i,j})_{1 \le i, j \le n}$ 定义了“Yuta 子序列”。

Rikka 将 $A$ 的一个子序列（记为 $a_{p_1}, a_{p_2}, \dots, a_{p_m}$，其中 $m \ge 1$ 且 $1 \le p_1 < p_2 < \dots < p_m \le n$）称为 Yuta 子序列，当且仅当对于所有的 $i = 1, 2, \dots, m-1$，都有 $M_{a_{p_i}, a_{p_{i+1}}} = 1$。统计不同 Yuta 子序列的数量在数据分析和数据恢复中具有深远的价值。

Rikka 认为这个任务太简单了，她想让它看起来更难、更具启发性。Rikka 知道一个 Yuta 子序列可能会在序列 $A$ 中出现多次，顶尖的程序员可能会使用类似 C++ 中的 map<vector<int>, bigInt> cnt 或 Java 中的 Map<ArrayList<Integer>, BigInteger> cnt 来存储所有 Yuta 子序列并统计它们的出现次数。

她将所有 Yuta 子序列出现次数的立方和，即 cnt 中所有第二项的立方和，称为 $A$ 关于 $M$ 的三阶系数。

现在，在向你展示了序列和 BRM 后，她希望你计算该序列关于给定 BRM 的三阶系数，结果对 $(10^9 + 7)$ 取模。

输入格式

输入包含多个测试用例，第一行包含一个整数 $T$ ($1 \le T \le 20$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 200$)，表示序列 $A$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)。 接下来的 $n$ 行描述了给定的 BRM，其中每一行包含 $n$ 个字符，第 $i$ 行的第 $j$ 个字符为 0 或 1，表示元素 $M_{i,j}$。

输出格式

对于每个测试用例，输出一行，包含一个整数，即给定序列关于给定 BRM 的三阶系数，对 $(10^9 + 7)$ 取模的结果。

样例

样例输入 1

1
4
1 2 1 2
1111
1111
1111
1111

样例输出 1

51