Niuniu likes cryptology. His friend, Gougou, sent him a graph as his birthday present. The graph is encoded, so Niuniu must answer a question to decode it. The graph has n vertices and m edges. Every vertex has a non-negative integer a_i. Here follows the question:
You need to assign each vertex another non-negative integer b_i, satisfying:
1. For an edge (u, v)，b_u ≠ b_v.
2. For a vertex u，0 ≤ b_u ≤ a_u.
3. b₁ xor b₂ xor ... xor b_n = C. (xor means exclusive OR)
What is the number of valid assignments modulo 998244353?
Can you help Niuniu answer the question?

The first line contains three integers n, m, C，which are the number of vertices, number of edges and the given number C.
The second line contains n non-negative integers, a1, a2, a3, ..., an, separated by a space.
The following m lines each line contains two different numbers, u and v, meaning that there is an edge between u and v. There are no multiple edges in the graph.
1 ≤ n ≤ 13, 0 ≤ m ≤ n(n-1)/2, 0 ≤ ai, C ≤ 1018

Print a single line with one number, which means the answer.

3 1 2
1 2 3
1 2

4