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 ai. Here follows the question:
You need to assign each vertex another non-negative integer bi, satisfying:
1. For an edge (u, v),bu ≠ bv.
2. For a vertex u,0 ≤ bu ≤ au.
3. b1 xor b2 xor ... xor bn = 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.