Problem Description

Xiao L has a directed graph. The vertices in the graph can be divided into $k$ layers. Layer $i$ has $n_i$ vertices. The numbers of vertices in layer $1$ and layer $k$ are the same, i.e., $n_1 = n_k$. For layer $j$ ($2 \leq j \leq k-1$), it holds that $n_1 \leq n_j \leq 2n_1$. For vertices in layer $j$ ($1 \leq j < k$), all edges starting from them only go to vertices in layer $j + 1$. There are no edges pointing to vertices in layer $1$, and vertices in layer $k$ do not have outgoing edges to any other vertices.

Now Xiao L wants to choose $n_1$ paths from this graph. Each path starts at a vertex in layer $1$ and ends at a vertex in layer $k$. Also, it is required that each vertex in the graph appears in at most one path. More specifically, number the vertices in each layer as $1,2,\ldots,n_i$. Then each path can be written as a $k$-tuple $(p_1,p_2,\ldots,p_k)$, meaning that this path passes through vertex $p_j$ ($1 \leq p_j \leq n_j$) in layer $j$ in order, and the vertex $p_j$ in layer $j$ ($1 \leq j < k$) has an edge to vertex $p_{j+1}$ in layer $j+1$.

Xiao L drew these paths on paper and found that they produce some intersection points. For two paths $P,Q$, let their edges between layer $j$ and layer $j+1$ be $(P_j,P_{j+1})$ and $(Q_j,Q_{j+1})$, respectively. If

then they are said to produce an intersection point after layer $j$. The number of intersections between two paths is the total number of intersection points they produce after layers $1,2,\ldots,k-1$. For the whole path selection (path scheme), its number of intersections is the sum of the numbers of intersections over all unordered pairs of distinct paths. For example, the figure below shows an example with $3$ paths and $3$ intersections, where the red points are intersections.

Xiao L now wants to know how many more path schemes with an even number of intersections there are than path schemes with an odd number of intersections. Two path schemes are considered the same if and only if their $k$-tuples, written in the order of the starting vertex indices in the first layer, are identical. Since the final result may be very large, please output it modulo $998244353$ (a large prime).

Input Format

This problem contains multiple test cases. The first line contains a positive integer $T$, indicating the number of test cases. For each test case:

The first line contains a positive integer $k$, indicating that there are $k$ layers of vertices.

The second line contains $k$ integers $n_1,n_2,\ldots,n_k$, indicating the number of vertices in each layer. It is guaranteed that $n_1=n_k$, and $n_1 \leq n_i \leq 2n_1$ ($2 \leq i \leq k-1$).

The third line contains $k-1$ integers $m_1,m_2,\ldots,m_{k-1}$, indicating the number of edges from layer $j$ to layer $j+1$. It is guaranteed that $m_j \leq n_j \times n_{j+1}$.

Then there are $k-1$ blocks of input. The $j$-th block ($1 \leq j < k$) contains $m_j$ lines. Each line has two integers $u,v$, meaning that vertex $u$ in layer $j$ has a directed edge to vertex $v$ in layer $j+1$.

The input guarantees that there are no multiple edges in the graph.

Output Format

Output $T$ lines. Each line contains one integer, the answer for that test case modulo $998244353$.

1
3
2 3 2
4 4
1 1 
1 2
2 1
2 3
1 2
2 1
3 1
3 2

1

Hint

[Sample Explanation #1]

There are $2$ schemes with an even number of intersections and $1$ scheme with an odd number of intersections, so the answer is $1$.

If you swap path $1$ and path $2$ in the table below, you will get the same scheme. For example, the scheme where path $1$ is $(2, 3, 1)$ and path $2$ is $(1, 1, 2)$ is the same as scheme $1$, so it will not be counted separately.

[Sample #2]

See the attachments xpath2.in and xpath2.ans.

The constraints of this sample are consistent with test points $7 \sim 8$.

[Sample #3]

See the attachments xpath3.in and xpath3.ans.

The constraints of this sample are consistent with test points $9 \sim 10$.

[Sample #4]

See the attachments xpath4.in and xpath4.ans.

The constraints of this sample are consistent with test points $14 \sim 15$.

[Constraints]

For all testdata: $2 \leq k \leq 100$, $2 \leq n_1 \leq 100$, $1 \leq T \leq 5$.

In each test point, it is guaranteed that there is only $1$ test case with $n_1 > 10$.

Special property A: For all $i$ ($2 \leq i \leq k-1$), $n_i = n_1$.

Special property B: It is guaranteed that the total number of path schemes is at most $1$.

Translated by ChatGPT 5