Vasylko and Sequences#4511
Vasylko is continuing his experiments with bitwise operations, this time again focusing on the operation. He randomly selects natural numbers a_1, a_2, \ldots, a_N. Then he asks his friend Vitaliy to provide a single number .
Upon receiving , Vasylko attempts to determine how many sequences of numbers b_1, b_2, \ldots, b_N exist such that:
For every (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.
Since the number of such sequences can be very large, Vasylko asks for your help. He asks you to calculate the number of these sequences modulo 10^9 + 7.
The first line contains the integer (1 \le N \le 100). The second line contains integers a_1, a_2, \ldots, a_N (1 \le a_i \le 10^9). The third line contains the integer (1 \le K \le 10^9).
Output a single integer: the number of sequences satisfying the above conditions, taken modulo 10^9 + 7.
Example 1