Metropolis 计算机网络由 $$$n$$$ 服务器组成,每个服务器都分配有一个从 $$$0$$$ 到 $$$2^k - 1$$$ 范围内的加密密钥。令 $$$c_i$$$ 为分配给第 $$$i$$$ 服务器的加密密钥。此外,$$$m$$$ 对服务器通过数据通信通道直接连接。由于加密算法的特殊性,只有当数据通信通道连接的两个服务器具有不同的加密密钥时,数据通信通道才能被认为是安全的。加密密钥的初始分配保证所有数据通信通道的安全。
您已获悉,一种新病毒正在互联网上积极传播,并且能够更改其感染的任何服务器的加密密钥。更具体地说,病毒体中包含一些在上述相同范围内的未知数字$$$x$$$,当服务器$$$i$$$被感染时,其加密密钥从$$$c_i$$$变为$$$c_i \oplus x$$$,其中$$$\oplus$$$表示按位异或运算。
可悲的是,您既不知道 $$$x$$$ 的数量,也不知道 Metropolis 的哪些服务器将被危险病毒感染,因此您决定计算所有数据通信通道保持安全的这种情况的数量。正式来说,您需要找到对的数量 $$$(A, x)$$$,其中 $$$A$$$ 是服务器集的某个(可能为空)子集,而 $$$x$$$ 是从 $$$0$$$ 到 $$$2^k - 1$$$ 范围内的某个数字,这样当所选子集中 $$$A$$$ 中的所有服务器且其他服务器都没有被包含该数字的病毒感染时$$$x$$$,所有数据通信通道保持安全。由于这个数字可能相当大,因此要求您求出其对 $$$10^9 + 7$$$ 取模的余数。
输入
输入的第一行包含三个整数 $$$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$$$),表示这些服务器通过数据通信通道连接。保证每对服务器最多在此列表中出现一次。
输出
唯一的输出行应包含一个整数 - 带有某个参数的病毒对某些服务器子集的安全感染数量,以 $$$10^9 + 7$$$ 为模。
示例
输入 #1
4 4 2 0 1 0 1 1 2 2 3 3 4 4 1
输出 #1
50
输入 #2
4 5 3 7 1 7 2 1 2 2 3 3 4 4 1 2 4
输出 #2
96
注意
考虑第一个例子。
病毒包含的数字 $$$x$$$ 的可能值为 $$$0$$$、$$$1$$$、$$$2$$$ 和 $$$3$$$。
对于值 $$$0$$$、$$$2$$$ 和 $$$3$$$,病毒可以感染服务器集的任何子集,这为每个值提供了 $$$16$$$ 对。包含数字 $$$1$$$ 的病毒可以感染所有服务器,也可以不感染任何服务器。这总共给我们 $$$16 + 2 + 16 + 16 = 50$$$ 对。