Counting Valid Vertex Labelings with XOR Constraint

You are given an undirected graph with n vertices and m edges. You are also given an array a of length n (i.e. a₁, a₂, …, a_n) and an integer C. Your task is to find the number of arrays b of length n satisfying the following conditions:

1. For every 1 ≤ i ≤ n, 0 ≤ b_i ≤ a_i.
2. For every edge (u, v) in the graph, b_u \(\neq\) b_v.
3. The XOR of all elements b₁ \oplus b₂ \oplus \cdots \oplus b_n = C, where \(\oplus\) denotes the bitwise XOR operation.

Output the answer modulo \(998244353\).

Note: The graph is not necessarily connected, and the vertices are 1-indexed.

inputFormat

The first line contains two integers n and m — the number of vertices and edges.

The second line contains n integers: a₁, a₂, …, a_n.

The third line contains a single integer C.

The following m lines each contain two integers u and v describing an undirected edge between vertices u and v.

outputFormat

Output a single integer, the number of valid arrays b satisfying the conditions, modulo \(998244353\).

sample

3 2
1 1 1
0
1 2
2 3

1