题目描述

For a known sequence, counting subsequences with a certain remarkable property can depict the sequence itself to a certain extent.

Now, Rikka has a sequence $A$ of length $n$ whose elements, denoted by $a_1, a_2, \cdots, a_n$, are positive integers in $[1, n]$. A bridging relation matrix (BRM) is a $n \times n$ logical matrix with elements from $\{0, 1\}$. Here Rikka defines a Yuta subsequence based on a given BRM, $M = (M_{i, j})_{1 \le i, j \le n}$.

Rikka calls a subsequence of $A$, denoted by $a_{p_1}, a_{p_2}, \cdots, a_{p_m}$ with $m\ge 1$ and $1 \le p_1 < p_2 < \cdots < p_m \le n$, a Yuta subsequence if and only if $M_{a_{p_i}, a_{p_{i + 1}}} = 1$ for $i = 1, 2, \cdots, m - 1$. Counting the number of different Yuta subsequences has a profound value in data analysis and data recovery.

Rikka thinks this task is too simple and she wants to make it look harder and more heuristic. Rikka knows that a Yuta subsequence may appear in the sequence $A$ several times and top programmers may use something like map<vector<int>, bigInt> cnt in C++ or Map<ArrayList<Integer>, BigInteger> cnt in Java to store all Yuta subsequences and count the numbers.

She calls the sum of the cubes of the numbers of occurrences for all Yuta subsequences, which is equal to the sum of cubes of all the second elements in cnt, the third coefficient of $A$ over $M$.

Now, after showing you the sequence and the BRM, she wants you to calculate the third coefficient of the sequence over the given BRM in modulo $(10^9 + 7)$.

输入格式

The input contains several test cases, and the first line contains a single integer $T$ ($1 \le T \le 20$), the number of test cases.

For each test case, the first line contains a single integer $n$ ($1 \le n \le 200$), the length of the sequence $A$.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$).

The following $n$ lines describe the given BRM, where each line of them has $n$ characters, and the $j$-th character in the $i$-th line of them is either $0$ or $1$, representing the element $M_{i, j}$.

输出格式

For each test case, output a single line with a single integer, the third coefficient of the given sequence over the given BRM in modulo $(10^9 + 7)$.

1
4
1 2 1 2
1111
1111
1111
1111

51