题目描述

给定一张 $n$ 个点 $m$ 条边的无向图和一个长度为 $n$ 的数组 $a_1, a_2, ··· , a_n$ 以及一个整数 $C$，你需要求出有 多少个长度为 $n$ 的数组 $b$ 满足：

1. $0 ≤ b_i ≤ a_i，∀1 ≤ i ≤ n$。

2. 对于每条边 $(u, v)，bu \neq bv$ 。

3. $b_1 ⊕ b_2 ⊕ · · · ⊕ b_n = C$ ，其中 ⊕ 代表异或。

答案对 $998244353$ 取模。

输入格式

第一行输入三个整数 $n, m, c$。

第二行输入 $n$ 个整数 $a_1, a_2,··· , a_n$。

接下来的 $m$ 行，每行输入两个正整数 $u, v$，表示一条无向边。

输出格式

一行一个整数表示答案。

输入样例1

3 1 2
1 2 3
1 2

输出样例1

4

输入样例2

4 6 2
7 11 14 0
1 2
1 3
2 3
2 4
4 1
4 3

输出样例1

44

样例解释

可行的 $b$ 数组有 $(0,1,3),(0,2,0),(1,0,3),(1,2,1)$ 四种

数据范围

对于所有数据，满足 $1 ≤ n ≤ 15,0 ≤ m ≤ \frac{n(n-1)}{2} , 0 ≤ a_i, C ≤ 10^{18}$。

$subtask1(20pts)$：$n ≤ 5, 0 ≤ a_i, C ≤ 15$。

$subtask2(50pts)$：$n ≤ 13$。

$subtask3(10pts)$：$m = 0$。

$subtask4(20pts)$：无特殊限制。