Rikka with Spanning Tree

Problem Description

Rikka is interested in researching traditional problems on particular graphs. Today, she chooses the task "counting the number of spanning trees in an undirected edge". With an array $a$ of length $n$, Rikka constructs an undirected graph with $\sum_{i=1}^n a_i$ vertices in the following way:

1. Construct an auxiliary array $B$: $B_0 = 0. B_i = B_{i-1}+a_i, \forall i \in [1,n].$
2. Assign a color to each vertex. The color of vertex $i$ is an integer $j$ which satisfies $i \in (B_{j-1},B_j]$.
3. For each pair $(i,j)(i<j)$, if vertex $i$ and $j$ have the same color, link an undirected edge between $i$ and $j$. In other words, Rikka constructs a graph which contains $n$ cliques, and the $i$th clique's size is $a_i$. Rikka finds that if $n>1$, the graph cannot be connected, and there must not be any spanning trees in it. To avoid this, Rikka adds extra $m$ edges $(u_i,v_i)$ to this graph. Now, Rikka wants to count the number of different spanning trees in this graph. Two spanning trees are different if and only if there is one edge which occurs in exactly one of the two trees.

Input

The first line contains a single integer $t(1 \leq t \leq 50)$, the number of the testcases. For each testcase, the first line contains two integers $n,m(1 \leq n \leq 200, 0 \leq m \leq 200)$. The second line contains $n$ integers $a_i(1 \leq a_i \leq 10^6)$. Then $m$ lines follows, each line contains two integers $u_i,v_i(1 \leq u_i,v_i \leq \sum_{k=1}^n a_i)$, which describes an extra edge. The input guarantees that:

1. There are at most $5$ testcases with $\max(n,m) > 50$.
2. The graph does not have multiplicate edges and self circle. i.e., $u_i \neq v_i$, $u_i,v_i$ have different colors and unordered pairs $(u_i,v_i)$ are different from each other.
3. The final graph is connected.

Output

For each testcase, output a single line with a single integer, the answer modulo $998244353$.

Sample Input

3

1 0

5

2 1

5 5

1 6

4 4

1 2 3 4

1 2

3 4

6 7

10 1

Sample Output

125

15625

296

Source

2018 Multi-University Training Contest 9