Decoding graphs
题号:NC17427
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

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.
示例1

输入

复制
3 1 2
1 2 3
1 2

输出

复制
4