К компьютерной сети Метрополии подключены \(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\).
Выходные данные
В единственной строке выходного файла выведите одно число — количество удачных исходов заражения какого-то подмножества компьютеров вирусом по модулю \(10^9 + 7\).
Примечание
Рассмотрим первый пример.
Возможные значения числа \(x\), содержащегося в вирусе, равны \(0\), \(1\), \(2\) и \(3\).
Для значений \(0\), \(2\) и \(3\) вирус может заразить любое подмножество серверов, что дает нам \(16\) исходов для каждого значения. Если же вирус содержит число \(1\), то он может заразить либо все серверы, либо ни одного. Таким образом, количество удачных исходов равно \(16 + 2 + 16 + 16 = 50\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4 2
0 1 0 1
1 2
2 3
3 4
4 1
|
50
|
|
2
|
4 5 3
7 1 7 2
1 2
2 3
3 4
4 1
2 4
|
96
|