{"raw_statement":[{"iden":"statement","content":"For a known sequence, counting subsequences with a certain remarkable property can depict the sequence itself to a certain extent.\n\nNow, 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 <= i , j <= n)$.\n\nRikka calls a subsequence of $A$, denoted by $a_{p_1}, a_{p_2}, \\\\\\\\cdots, a_{p_m}$ with $m >= 1$ and $1 <= p_1 < p_2 < \\\\\\\\cdots < p_m <= 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.\n\nRikka 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, bigInt> cnt_ in C++ or _Map, BigInteger> cnt_ in Java to store all Yuta subsequences and count the numbers.\n\nShe 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$.\n\nNow, 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)$.\n\nThe input contains several test cases, and the first line contains a single integer $T$ ($1 <= T <= 20$), the number of test cases.\n\nFor each test case, the first line contains a single integer $n$ ($1 <= n <= 200$), the length of the sequence $A$.\n\nThe second line contains $n$ integers $a_1, a_2, \\\\\\\\cdots, a_n$ ($1 <= a_i <= n$).\n\nThe 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}$.\n\nFor 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)$.\n\n"},{"iden":"input","content":"The input contains several test cases, and the first line contains a single integer $T$ ($1 <= T <= 20$), the number of test cases.For each test case, the first line contains a single integer $n$ ($1 <= n <= 200$), the length of the sequence $A$.The second line contains $n$ integers $a_1, a_2, \\\\\\\\cdots, a_n$ ($1 <= a_i <= 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}$."},{"iden":"output","content":"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)$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of sequence $ A = (a_1, a_2, \\dots, a_n) $, where $ a_i \\in [1, n] $.  \nLet $ M \\in \\{0,1\\}^{n \\times n} $ be the Bridging Relation Matrix (BRM), where $ M_{i,j} = 1 $ indicates a valid transition from value $ i $ to value $ j $.  \n\nA **Yuta subsequence** is a non-empty subsequence $ A' = (a_{p_1}, a_{p_2}, \\dots, a_{p_m}) $ with $ 1 \\le p_1 < p_2 < \\dots < p_m \\le n $ and $ m \\ge 1 $, such that $ M_{a_{p_i}, a_{p_{i+1}}} = 1 $ for all $ i \\in \\{1, 2, \\dots, m-1\\} $.  \n\nLet $ \\mathcal{S} $ be the multiset of all Yuta subsequences in $ A $, and for each distinct Yuta subsequence $ s \\in \\mathcal{S} $, let $ c(s) $ denote its number of occurrences (i.e., the number of distinct index sequences producing $ s $).  \n\n**Constraints**  \n1. $ 1 \\le T \\le 20 $  \n2. $ 1 \\le n \\le 200 $  \n3. $ 1 \\le a_i \\le n $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. $ M_{i,j} \\in \\{0,1\\} $ for all $ i,j \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nCompute:  \n$$\n\\sum_{s \\in \\mathcal{S}} \\left(c(s)\\right)^3 \\mod (10^9 + 7)\n$$","simple_statement":"Count all non-empty subsequences where each adjacent pair (a[i], a[j]) has M[a[i]][a[j]] = 1. For each such subsequence, count how many times it appears in the array. Then sum the cube of each count, modulo 10^9+7.","has_page_source":false}