Vasylko and Sequences
Vasylko is continuing his experiments with bitwise operations, focusing once again on the XOR operation. He starts by randomly selecting N natural numbers, denoted as a_1, a_2, ..., a_N. Then, he asks his friend Vitaliy to provide a single number K.
Once he receives the number K, Vasylko attempts to determine how many sequences of numbers b_1, b_2, ..., b_N exist that meet the following criteria:
Each b_i satisfies 0 ≤ b_i ≤ a_i, for 1 ≤ i ≤ N.
The XOR of all b_i values, i.e., b_1
b_2
...
b_N, equals K.
Given that the number of such sequences can be extremely large, Vasylko seeks your assistance. He requests that you find the number of these sequences, calculated modulo 10^9+7.
Input
The first line contains the integer N, where 1 ≤ N ≤ 100. The second line contains N integers a_1, a_2, ..., a_N, with each a_i satisfying 1 ≤ a_i ≤ 10^9, for 1 ≤ i ≤ N. The third line contains the integer K, where 1 ≤ K ≤ 10^9.
Output
Output a single integer, which is the number of sequences that satisfy the conditions described above, taken modulo 10^9+7.