Василько і послідовності#4511
Василько продовжує свої експерименти із бітовими операціями. Цього разу він знову працює над операцією . Спочатку він випадковим чином вибирає натуральних чисел a_1, a_2, \ldots, a_N, після цього просить свого друга Віталія назвати єдине число .
Отримавши число , він намагається порахувати, скільки існує таких послідовностей чисел b_1, b_2, \ldots, b_N, для яких виконуються наступні умови:
Для кожного (1 \le i \le N), 0 \le b_i \le a_i.
b_1\ \mathrm{XOR}\ b_2\ \mathrm{XOR}\ \ldots\ \mathrm{XOR}\ b_N = K.
Оскільки їхня кількість може бути дуже великою, він просить вас допомогти йому у цьому. Щоб вам було простіше, він просить знайти цю кількість за модулем 10^9 + 7.
У першому рядку задано число (1 \le N \le 100). У наступному рядку задано чисел a_1, a_2, \ldots, a_N (1 \le a_i \le 10^9) . У третьому рядку задано єдине число (1 \le K \le 10^9) .
Виведіть єдине число — кількість шуканих послідовностей, які задовольняють описані вище умови, за модулем 10^9 + 7.
Приклад 1