9676: Matrix Lottery

There is a lottery box, and the lottery action corresponds to an $n\times n$ matrix. Each cell in the matrix has a light bulb, which is initially turned off. Each time a lottery is drawn, a specific light bulb will be attempted to be turned on, each with a fixed probability, even if the light bulb is already on. Once a light bulb is turned on, it will remain on. In other words, each time a lottery is drawn, there is a probability of pi,jp_{i, j}pi,j of selecting the light bulb in the $i$-th row and $j$-th column, or indexed (i,j)(i, j)(i,j), and attempting to turn it on (1≤i,j≤n1 \leq i, j \leq n1≤i,j≤n). If the light is already on, this operation is ignored.

The first line contains an integer $T$ (1≤T≤2001 \leq T \leq 2001≤T≤200), indicating the number of test cases.
Then follow $T$ test cases. For each test case:
The first line contains two integers $n$ and $q$ ($2\le n\le 7$, 1<=q<=10⁵).
The next $n$ lines describe the probabilities of selecting each cell. The $i$-th line contains $n$ integers wi,1,wi,2,…,wi,nw_{i, 1}, w_{i, 2}, \ldots, w_{i, n}wi,1,wi,2,…,wi,n, representing that pi,j=wi,jWp_{i, j} = \frac{w_{i, j}}{W}pi,j=Wwi,j, where    .
The next $(2n+2)$ lines describe the line with respect to the gifts. The $i$-th line contains $2n$ integers xi,1,yi,1,xi,2,yi,2,…,xi,n,yi,nx_{i, 1}, y_{i, 1}, x_{i, 2}, y_{i, 2}, \ldots, x_{i, n}, y_{i, n}xi,1,yi,1,xi,2,yi,2,…,xi,n,yi,n, representing that there are exactly $n$ distinct cells with indices (xi,1,yi,1),(xi,2,yi,2),…,(xi,n,yi,n)(x_{i, 1}, y_{i, 1}), (x_{i, 2}, y_{i, 2}), \ldots, (x_{i, n}, y_{i, n})(xi,1,yi,1),(xi,2,yi,2),…,(xi,n,yi,n) lying on the line with respect to the gift $(i-1)$. It is guaranteed that all possible lines (i.e. $n$ rows, $n$ columns and $2$ diagonals) are given.
The next line contains $q$ integers t1,t2,…,tqt_1, t_2, \ldots, t_qt1,t2,…,tq .
It is guaranteed that the number of test cases for $n=4,5,6,7$ does not exceed $50,10,3,1$ respectively.
It is also guaranteed that the sum of $q$ over $T$ test cases does not exceed 5*10⁵.

For each test case, output $q$ lines, the $i$-th line of which contains an integer, representing your answer to the $i$-th query.
It can be proved that the expected value is always a rational number. Additionally, under the constraints of this problem, it can also be proved that when that value is represented as an irreducible fraction $u/d$, we have . Thus, there is a unique integer $f$ (0<=f<10⁹+7) such that . This $f$ is what we need.