Problem Description

Given an undirected graph with $n$ vertices and $m$ edges, an array $a_1, a_2, \cdots , a_n$ of length $n$, and an integer $C$, you need to count how many arrays $b$ of length $n$ satisfy:

1. $0 \le b_i \le a_i, \forall 1 \le i \le n$。
2. For every edge $(u, v)$, $b_u \ne b_v$。
3. $b_1 \oplus b_2 \oplus \cdots \oplus b_n = C$, where $\oplus$ denotes bitwise XOR.

Output the answer modulo $998244353$。

Input Format

The first line contains three integers $n, m, c$。

The second line contains $n$ integers $a_1, a_2, \cdots , a_n$。

The next $m$ lines each contain two positive integers $u, v$, representing an undirected edge。

Output Format

Output one integer, the answer。

3 1 2
1 2 3
1 2

4

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

44

Hint

There are four feasible arrays $b$: $(0, 1, 3), (0, 2, 0), (1, 0, 3), (1, 2, 1)$。

For all testdata, $1 \le n \le 15$, $0 \le m \le \frac{n(n-1)}{2}$, $0 \le a_i, C \le 10^{18}$。

• Subtask 1 (20pts): $n \le 5$, $0 \le a_i, C \le 15$。
• Subtask 2 (50pts): $n \le 13$。
• Subtask 3 (10pts): $m = 0$。
• Subtask 4 (20pts): No special constraints。

Translated by ChatGPT 5