3198. 画

【题目描述】

你有一张 n 个点 m 条无向边的简单无向图（无重边和自环），点标号为1; 2; ...; n。你要给图中每一个点染上一种颜色，设图中第 i 个点被染上的颜色为 coli，则图的美丽值为 col1 ⊕ col2 ⊕ col3 ⊕... ⊕ coln （ ⊕ 表示异或和）。每一个点染上的颜色 coli ，必须是 0; 1; 2; ...; limiti 中的一个整数（limiti 为输入给定的数）。

一个图是不单调的，当且仅当对于所有边 (u; v)，满足 colu != colv。问有多少种不同的染色方案使得染色后的图不单调，并且美丽值为 C（C为输入给定的数）。两种染色方案是不同的当且仅当存在至少一个点 u，使得 u在两张图中的颜色 colu 不同。由于答案可能较大，请输出答案对 998244353 取模的结果。

【输入格式】

第一行三个整数 n; m; C，分别表示图的点数、边数和美丽值 C。

第二行 n 个整数，分别表示 limit1; limit2; limit3; ...; limitn。

第 3 到 m + 2 行每行两个整数 u; v 表示一条无向边。

保证输入的图是无重边和自环的简单无向图。

【输出格式】

一行一个整数表示答案。

【样例输入】

3 2 3
3 6 5
1 2
1 3

【样例输出】

15

【提示】

对于所有测试包均满足 1 ≤ n ≤ 15; 0 ≤ m ≤ n*(n-1)/2; 0 ≤ C; limi,ti ≤10e18; 1 ≤ u; v ≤ n。