CF1039C.Network Safety

The Metropolis computer network consists of $n$ servers, each has an encryption key in the range from $0$ to $2^k - 1$ assigned to it. Let $c_i$ be the encryption key assigned to the $i$-th server. Additionally, $m$ pairs of servers are directly connected via a data communication channel. Because of the encryption algorithms specifics, a data communication channel can only be considered safe if the two servers it connects have distinct encryption keys. The initial assignment of encryption keys is guaranteed to keep all data communication channels safe.

You have been informed that a new virus is actively spreading across the internet, and it is capable to change the encryption key of any server it infects. More specifically, the virus body contains some unknown number $x$ in the same aforementioned range, and when server $i$ is infected, its encryption key changes from $c_i$ to $c_i \oplus x$, where $\oplus$ denotes the bitwise XOR operation.

Sadly, you know neither the number $x$ nor which servers of Metropolis are going to be infected by the dangerous virus, so you have decided to count the number of such situations in which all data communication channels remain safe. Formally speaking, you need to find the number of pairs $(A, x)$, where $A$ is some (possibly empty) subset of the set of servers and $x$ is some number in the range from $0$ to $2^k - 1$, such that when all servers from the chosen subset $A$ and none of the others are infected by a virus containing the number $x$, all data communication channels remain safe. Since this number can be quite big, you are asked to find its remainder modulo $10^9 + 7$.

Metropolis 计算机网络由 $n$ 台服务器组成，每台服务器被分配一个取值范围在 $0$ 到 $2^k - 1$ 之间的加密密钥。设第 $i$ 台服务器的加密密钥为 $c_i$。此外，有 $m$ 对服务器通过数据通信信道直接相连。由于加密算法的特性，仅当一条数据通信信道所连接的两台服务器具有不同的加密密钥时，该信道才被视为安全的。初始的密钥分配保证了所有数据通信信道均是安全的。

你已获悉一种新型病毒正在互联网上迅速传播，该病毒能够修改其感染的任意服务器的加密密钥。更具体地说，病毒体内包含某个未知数 $x$（同样在 $0$ 到 $2^k - 1$ 的范围内），当服务器 $i$ 被感染时，其加密密钥将由 $c_i$ 变为 $c_i \oplus x$，其中 $\oplus$ 表示按位异或运算。

遗憾的是，你既不知道该未知数 $x$ 的值，也不知道 Metropolis 网络中哪些服务器将被这种危险病毒所感染。因此，你决定统计所有可能的情形数目，使得在这些情形下，所有数据通信信道仍保持安全。形式化地讲，你需要计算满足如下条件的二元组 $(A, x)$ 的个数：其中 $A$ 是服务器集合的某个（可能为空的）子集，$x$ 是 $0$ 到 $2^k - 1$ 范围内的某个整数；当且仅当 $A$ 中的所有服务器被携带数字 $x$ 的病毒所感染时，所有数据通信信道仍保持安全。由于该数目可能非常大，你只需输出其对 $10^9 + 7$ 取模的结果。

The first line of input contains three integers $n$, $m$ and $k$ ($1 \leq n \leq 500\,000$, $0 \leq m \leq \min(\frac{n(n - 1)}{2}, 500\,000)$, $0 \leq k \leq 60$) — the number of servers, the number of pairs of servers directly connected by a data communication channel, and the parameter $k$, which defines the range of possible values for encryption keys.

The next line contains $n$ integers $c_i$ ($0 \leq c_i \leq 2^k - 1$), the $i$-th of which is the encryption key used by the $i$-th server.

The next $m$ lines contain two integers $u_i$ and $v_i$ each ($1 \leq u_i, v_i \leq n$, $u_i \ne v_i$) denoting that those servers are connected by a data communication channel. It is guaranteed that each pair of servers appears in this list at most once.

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n \leq 500\,000$，$0 \leq m \leq \min(\frac{n(n - 1)}{2}, 500\,000)$，$0 \leq k \leq 60$），分别表示服务器的数量、直接通过数据通信信道相连的服务器对数，以及参数 $k$（它定义了加密密钥可能取值的范围）。

第二行包含 $n$ 个整数 $c_i$（$0 \leq c_i \leq 2^k - 1$），其中第 $i$ 个数表示第 $i$ 台服务器所使用的加密密钥。

接下来的 $m$ 行每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，$u_i \ne v_i$），表示这两台服务器之间存在一条数据通信信道。保证每对服务器在此列表中至多出现一次。

The only output line should contain a single integer — the number of safe infections of some subset of servers by a virus with some parameter, modulo $10^9 + 7$.

唯一的一行输出应包含一个整数——即病毒以某一参数感染某服务器子集的安全感染方案数，对 $10^9 + 7$ 取模。

Consider the first example.

Possible values for the number $x$ contained by the virus are $0$, $1$, $2$ and $3$.

For values $0$, $2$ and $3$ the virus can infect any subset of the set of servers, which gives us $16$ pairs for each values. A virus containing the number $1$ can infect either all of the servers, or none. This gives us $16 + 2 + 16 + 16 = 50$ pairs in total.

考虑第一个例子。

病毒所含数字 $x$ 的可能取值为 $0$、$1$、$2$ 和 $3$。

对于取值 $0$、$2$ 和 $3$，病毒可以感染服务器集合的任意子集，每种取值对应 $16$ 个数对。而含数字 $1$ 的病毒只能感染全部服务器或不感染任何服务器，因此仅对应 $2$ 个数对。综上，总数对为 $16 + 2 + 16 + 16 = 50$。