题目描述

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

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

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

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, \cdots, a_n$（$1 \le a_i \le n$）。

接下来的 $n$ 行描述给定的 BRM，每行包含 $n$ 个字符，其中第 $i$ 行的第 $j$ 个字符为 $0$ 或 $1$，表示元素 $M_{i, j}$。

输出格式

对于每组测试数据，输出一行一个整数，表示给定序列关于给定 BRM 的第三系数对 $(10^9 + 7)$ 取模的结果。

1
4
1 2 1 2
1111
1111
1111
1111

51

提示

翻译由 DeepSeek V4 Pro 完成