Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Given an array C of M integers and a square matrix A (with integer entries) of dimension $N \times N,$ verify whether the following equation is true,

$C_{0} I_{N} + C_{1} A + C_{2} A^{2} + \dots C_{M-1} A^{M-1} \equiv 0_{N} \pmod{998244353}$

where 0_{N} is the square null matrix (matrix in which all elements are zero) and I_{N} is the identity matrix, both having dimensions $N \times N$.

Note:
Two matrices A, B each with integer entries are said to be congruent modulo M iff all entries of A - B are divisible by M. This is denoted as $A \equiv B \pmod{M}$.
Since the input-output is large, prefer using fast input-output methods.

------ Input Format ------

• The first line contains T denoting the number of test cases. Then the test cases follow.
• The first line of each test case contains a single integer M denoting the length of C.
• The second line of each testcase contains $M space separated integers, C_{0}, C_{1}, \dots C_{M-1}$ representing the array C.
• The third line of each testcase contains a single integer N denoting the size of the square matrix A.
• The i-th line of the next $N lines contains N space-separated integers A_{i,1}, A_{i,2}, \dots, A_{i,N}$ denoting the elements of the i-th row of the matrix A.

------ Output Format ------

For each test case, output on a single line YES if the equation $C_{0} I_{n} + C_{1} A + C_{2} A^{2} + \dots C_{M-1} A^{M-1} \equiv 0_{N} \pmod{998244353}$ satisfies, and NO otherwise.

Output is case insensitive, i.e., you may print each character of the string in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

------ Constraints ------

$1 ≤ T ≤ 200$
$1 ≤ N ≤ 1000$
$1 ≤ M ≤ 11$
$0 ≤ C_{i} < 998244353$
$0 ≤ A_{i,j} < 998244353$
- Sum of $N$ over all test cases does not exceed $2000$.

------ subtasks ------

Subtask 1 (100 points): Original constraints

----- Sample Input 1 ------
2
3
998244351 998244348 1
2
1 2
3 4
3
998244351 998244348 1
2
1 1
1 1
----- Sample Output 1 ------
YES
NO
----- explanation 1 ------
Both test cases have the same co-efficients. Since $998244351 \equiv -2 \pmod{998244353}$ and $998244348 \equiv -5 \pmod{998244353}$, for convenience of explanation, we shall take the co-efficients as $-2, -5, 1$. Note that this does not affect the answer.

Test case $1$: The given matrix, $A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}$, satisfies the equation $-2 I_{2} -5 A + A^{2} = 0_{2}$, so the answer is YES.

Test case $2$: For the given matrix, $A = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}$, the left hand side of the equation evaluates to, $-2I_{2} - 5A + A^{2} = \begin{bmatrix}-5 & -3\\-3 & -5\end{bmatrix}$. Clearly none of the entries are divisible by $998244353$, so the answer is NO.

见题面

见题面