C. Безопасность сети
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

К компьютерной сети Метрополии подключены $$$n$$$ серверов, каждому из которых назначен некоторый ключ шифрования, выбранный в диапазоне от $$$0$$$ до $$$2^k - 1$$$ включительно. Обозначим через $$$c_i$$$ ключ шифрования, назначенный $$$i$$$-му серверу. Также некоторые $$$m$$$ пар серверов напрямую соединены каналом передачи данных. Из-за особенностей используемых алгоритмов шифрования канал передачи данных безопасен, только если два соединённых этим каналом сервера используют различные ключи шифрования. Изначально ключи шифрования выбраны таким образом, что все каналы передачи данных безопасны.

Вам стало известно, что по интернету активно распространяется новый вирус, который при заражении им какого-либо сервера Метрополии изменяет его ключ шифрования. А именно, в теле вируса хранится некоторое неизвестное вам число $$$x$$$, выбранное в том же диапазоне, и если вирусом заразится сервер $$$i$$$, то его ключ шифрования изменится с $$$c_i$$$ на $$$c_i \oplus x$$$, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

К сожалению, вы не знаете ни число $$$x$$$, ни какие именно серверы Метрополии будут заражены опасным вирусом, поэтому решили посчитать количество вариантов, при которых безопасность каналов нарушена не будет. Формально, вам требуется найти количество пар $$$(A, x)$$$, где $$$A$$$ — некоторое подмножество серверов (возможно пустое), а $$$x$$$ — возможное значение внутреннего параметра вируса в диапазоне от $$$0$$$ до $$$2^k - 1$$$ включительно, таких что если вирус с параметром $$$x$$$ заразит компьютеры из подмножества $$$A$$$, а остальные компьютеры заражены не будут, то все каналы передачи данных останутся безопасными. Поскольку эта величина может быть достаточно большой, найдите остаток от её деления на $$$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$$$.

Примеры
Входные данные
4 4 2
0 1 0 1
1 2
2 3
3 4
4 1
Выходные данные
50
Входные данные
4 5 3
7 1 7 2
1 2
2 3
3 4
4 1
2 4
Выходные данные
96
Примечание

Рассмотрим первый пример.

Возможные значения числа $$$x$$$, содержащегося в вирусе, равны $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$.

Для значений $$$0$$$, $$$2$$$ и $$$3$$$ вирус может заразить любое подмножество серверов, что дает нам $$$16$$$ исходов для каждого значения. Если же вирус содержит число $$$1$$$, то он может заразить либо все серверы, либо ни одного. Таким образом, количество удачных исходов равно $$$16 + 2 + 16 + 16 = 50$$$.