Василий продолжает свои эксперименты с битовыми операциями. В этот раз он опять работает с операцией XOR. Сначала он случайным образом выбирает N натуральных чисел a_1, a_2, ..., a_N, после чего просит своего друга Виталия назвать единственное число K.
Плучив число K он пытается посчитать сколько существует таких последовательностей чисел b_1, b_2, ..., b_N, для которых выполняются сследующие условия:
0 ≤ b_i ≤ a_i, для 1 ≤ i ≤ N.
b_1
b_2
...
b_N = K.
Так как их количество может быть очень большим, он просит Вас помочь ему в этом. Чтобы Вам было проще он просит найти это количество по модулю 10^9+7.
В первой строке задано число N, 1 ≤ N ≤ 100. В стледующей строке задано N чисел a_1, a_2, ..., a_N, 1 ≤ a_i ≤ 10^9, 1 ≤ i ≤ N. В третьей строке задано едиственное число K, 1 ≤ K ≤ 10^9.
Выведите единственное число - количество последовательностей, которые удовлетворяют описанные выше условия, по модулю 10^9+7.