Even–Odd Intersection Difference of Path Schemes

You are given a layered directed graph. The vertices are partitioned into k layers. The i-th layer has n_i vertices. It is guaranteed that the first and the last layers have the same number of vertices, i.e. n₁ = n_k, and for every intermediate layer j (2 ≤ j ≤ k–1) the number of vertices satisfies n₁ ≤ n_j ≤ 2n₁.

For every layer j (1 ≤ j < k), each vertex in layer j has some outgoing edges that only connect to vertices in layer j+1. There are no incoming edges to vertices in layer 1 and no outgoing edges from vertices in layer k.

You are to select n₁ paths such that:

1. Each path starts at a vertex in layer 1 and ends at a vertex in layer k.
2. If we number the vertices in layer i as 1, 2, …, n_i, then every path can be represented as a k-tuple (p₁, p₂, …, p_k) where 1 ≤ p_j ≤ n_j, and for every 1 ≤ j < k, there is an edge from the p_j-th vertex in layer j to the p_j+1-th vertex in layer j+1.
3. No vertex is used in more than one path.

When drawing the n₁ paths according to their vertex positions (with vertices in each layer arranged from left to right in increasing order), some intersections may occur. For any two distinct paths P and Q, denote the edge between layers j and j+1 on path P by (P_j, P_j+1) and on Q by (Q_j, Q_j+1). They form an intersection between layers j and j+1 if

The total number of intersections in a scheme is defined as the sum, over all unordered pairs of different paths, of the number of intersections they form (i.e. the sum over layers j = 1, 2, …, k–1 of the intersections between each pair). We say that a scheme has even (or odd) number of intersections depending on the parity of this total number.

Your task is to compute the value of (number of schemes with even intersections) minus (number of schemes with odd intersections), modulo 998244353.

Note

Two schemes are considered the same if the ordered list of k-tuples (ordered by the starting vertex number in layer 1) is identical.

Input Format

The input starts with an integer T (T ≥ 1) denoting the number of test cases. For each test case:

• The first line contains an integer k (the number of layers).
• The second line contains k space‐separated integers: n₁ n₂ … n_k.
• Then for each layer j from 1 to k–1, there are n_j lines. Each of these lines contains n_j+1 integers (each either 0 or 1) where the i-th line represents the availability of an edge from the i-th vertex in layer j to each vertex (from 1 to n_j+1) in layer j+1. A value of 1 indicates that the edge exists.

Output Format

For each test case, output a single integer — the required difference modulo 998244353.

Explanation

One way to think of the problem is as follows. For each layer transition (from layer j to j+1), you choose an injection f from the indices {1, 2, …, n_j} to {1, 2, …, n_j+1} such that for each i (1 ≤ i ≤ n_j), the edge from the i-th vertex of layer j to the f(i)-th vertex of layer j+1 exists. The sign of such an injection is defined as the sign of the permutation induced when considering the sequence (f(1), f(2), …, f(n_j)). A crossing between two paths on a layer boundary corresponds exactly to an inversion in this sequence. It turns out that the parity of the total number of intersections in a scheme is equal to the product of the signs of the injections chosen for each layer transition. Hence, the required answer is the product (over layer transitions) of the sums, over all valid injections at that layer, of the sign of the injection. (See the formulas below in LaTeX.)

The contribution for one layer transition can be written as:

And the final answer is:

inputFormat

The first line contains an integer T, the number of test cases. Then for each test case:

• A line containing an integer k (the number of layers).
• A line with k space‐separated integers: n₁ n₂ … n_k (with n₁ = n_k and n₁ ≤ n_j ≤ 2n₁ for 2 ≤ j ≤ k–1).
• For each layer j from 1 to k–1, n_j lines follow. Each of these lines contains n_j+1 integers (0 or 1) separated by spaces, indicating whether an edge exists from that vertex in layer j to each vertex in layer j+1.

outputFormat

For each test case, output a single integer — the difference between the number of schemes with an even number of intersections and the number of schemes with an odd number of intersections, modulo 998244353.

sample

1
2
2 2
1 1
1 0

998244352