Description

Link has a directed graph. Vertices in the graph can be divided into $k$ layers, with $n_i$ vertices in the $i$th layer. The $1$st layer and the $k$th layer have the same number of vertices, or $n_1=n_k$, and for the $j$th $(2 \leq j \leq k-1)$ layer, $n_1 \leq n_i \leq 2n_1(2 \leq i \leq k-1)$. For vertices in the $j$th $(1 \leq j < k)$ layer, edges pointing from them only point to vertices in the $j+1$th layer. No edges point to vertices in the $1$st layer, nor do vertices in the $k$th layer have any edges pointing from them.

Link would choose $n_1$ paths from the graph. Each path starts from a vertex in the $1$st layer and ends in a vertex in the $k$th layer, and it is required that each vertex in the graph would only appear in at most one of the paths. More specifically, if vertices in each layer are numbered as $1,2,...,n_i$, then each path could be written as a $k$-tuple $(p_1,p_2,...,p_k)$, denoting that this path passes through vertex number $p_j(1 \leq p_j \leq n_j)$ in the $j$th layer successively, and there exists a directed edge from vertex $p_j$ in layer $j(1 \leq j < k)$ to vertex $p_{j+1}$ in layer $j+1$.

Link draws these paths on a paper and found them forming some intersections. For two paths $P,Q$, let their edges between layer $j$ and $j+1$ be $(P_j,P_{j+1})$ and $(Q_j,Q_{j+1})$, if:

then we say that they form an intersection after the $j$th layer. The total number of intersections between two paths is the sum of number of intersections formed between them after layers $1,2,...,k-1$. For the whole path arrangement, its intersection count equals the sum of number of intersections between all distinct pairs of paths. For example, the figure below is a case with $3$ paths and a total of $3$ intersections, with red points indicating the intersections.

Link now wonders how many more arrangements with an even number of intersections are there than those with an odd number of intersections. Two path arrangements are the same if and only if the $k$-tuples of their $n_i$ paths ordered by their starting points' number in the first layer are all the same. Since the result may be large, please output it modulo $998244353$ (a large prime).

Input Format

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

The first line contains an integers $k$, indicating there are $k$ layers of vertices in total.

The second line contains $k$ integers $n_1,n_2,\dots,n_k$, representing in order 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,\dots,m_{k-1}$, representing in order the number of directed edges from layer $j(1 \leq j < k)$ to layer $j+1$. It is guaranteed that $m_j \leq n_j \times n_{j+1}$.

This is followed by $k-1$ segments of input. The $j$th $(1 \leq j < k)$ segment contains $m_j$ lines, each line consists of two integers $u,v$, indicating there's a directed edge from vertex $u$ in layer $j$ to vertex $v$ in layer $j+1$.

It is guaranteed that multiple edges don't exist in graphs.

Output Format

Output consists of $T$ lines, one integer each, indicating the answer to 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

Sample Explanation 1

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

Exchanging path $1$ and path $2$ in the table below results in the same path arrangement. For example, an arrangement with $(2,3,1)$ as path $1$ and $(1,1,2) as path $2$ is the same as arrangment $1$, so won't be included in the answer.

Sample 2

See files xpath2.in and xpath2.ans under participant directory.
Constraints of this sample is the same as test cases $7 \sim 8$.

Sample 3

See files xpath3.in and xpath2.ans under participant directory.
Constraints of this sample is the same as test cases $9 \sim 10$.

Sample 4

See files xpath4.in and xpath4.ans under participant directory.
Constraints of this sample is the same as test cases $14 \sim 15$.

Constraints and Specification

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

In each test, it is guaranteed that only one test case has $n_1 > 10$.

Special case $\text{A}$: for all $i(2 \leq i \leq k-1)$, $n_i=n_1$.
Special case $\text{B}$: it is assured that there are at most $1$ valid path arrangement.