Given an undirected graph with $n$ vertices and $m$ edges, an array $a$ of length $n$, and an integer $C$, you need to find the number of arrays $b$ of length $n$ that satisfy:

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

The answer should be taken modulo $998244353$.

Input

The first line contains three integers $n, m, C$. The second line contains $n$ integers $a_1, a_2, \dots, a_n$. The next $m$ lines each contain two positive integers $u, v$, representing an undirected edge.

Output

Output a single integer representing the answer.

Examples

Input 1

3 1 2
1 2 3
1 2

Output 1

4

Note

The valid arrays $b$ are $(0, 1, 3), (0, 2, 0), (1, 0, 3), (1, 2, 1)$.

Constraints

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

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