G. Destroy the NPS
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Brigadier is destroying a nuclear power station.

There are $$$n$$$ cores and $$$m$$$ data cables in the nuclear power station. The $$$i$$$-th core has energy $$$a_i$$$, each cable connects two different cores. To destroy the station, the Brigadier needs to create enough interference in it. For a data cable connecting cores $$$u,v$$$, it produces interference with value $$$a_u \text{ XOR } a_v$$$. The total interference in the station is the sum of the interference produced by all data cables.

To help the Brigadier destroy the station, Mari Gold hacked into the factory system and made a button. Each time the button is pressed, the following steps are done in order:

  1. Uniformly at random generate an integer $$$x$$$ from $$$1$$$ to $$$n$$$;
  2. Uniformly at random generate an integer $$$y$$$ from $$$1$$$ to $$$n$$$;
  3. Swap the energy values $$$a_x,a_y$$$ of the $$$x$$$-th core and the $$$y$$$-th core.

The Brigadier wants to know the expected value of the total interference in the station after pressing the button $$$k$$$ times in a row.

As the answer may be very large, you only need to output it modulo $$$998244353$$$$$$^{\text{∗}}$$$.

$$$^{\text{∗}}$$$Let $$$M=998244353$$$:

  • It can be proved that the answer can be written as an irreducible fraction $$$\frac{p}{q}$$$.
  • There exists a unique integer $$$r$$$ such that $$$0 \leq r \lt M$$$ and $$$q \cdot r \equiv p \pmod M$$$.
  • $$$r$$$ is the number you need to output.
Input

Each test file contains multiple test cases. The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 10^3)$$$, the number of test cases.

For each test case, the first line contains three positive integers $$$n,m,k$$$ $$$(4 \leq n \leq 2 \times 10^5,1 \leq m \leq 5 \times 10^5,0 \leq k \leq 10^{18})$$$, denoting the number of cores, the number of data cables, and the number of times the button is pressed.

The second line contains $$$n$$$ integers $$$a_i$$$ $$$(0 \leq a_i \lt 2^{30})$$$, denoting the energy of each core.

The next $$$m$$$ lines each contain two integers $$$u,v$$$ $$$(1 \leq u,v \leq n,u \neq v)$$$, denoting a data cable whose two ends are connected to cores $$$u,v$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^5$$$, and the sum of $$$m$$$ does not exceed $$$5 \times 10^5$$$.

Output

For each test case, output one line containing one integer, the expected value of the total interference modulo $$$998244353$$$.

Examples
Input
1
4 3 1
1 2 4 8
1 2
2 3
3 4
Output
249561110
Input
1
4 6 2
0 2 1 3
4 2
3 4
1 2
2 1
2 4
3 2
Output
62390284
Note

In Sample 1, the two random choices when pressing the button and the corresponding total interference values are shown in the table below:

1234
121201821
220212127
318212125
421272521

The sum of the total interference values over all cases is $$$348$$$, so the expected value is $$$\frac{348}{16}=\frac{87}{4} \equiv 249561110 \pmod {998244353}$$$.