A sequence of integers $$$a_1, a_2, \ldots, a_n$$$ is given. A partition of the sequence $$$a_1, a_2, \ldots, a_n$$$ is defined as a set of its contiguous intervals, such that each element belongs to exactly one interval.
The xor of a contiguous interval of this sequence is defined as the bitwise xor of the numbers in this interval. The value of a partition of the sequence is defined as the product of xors of the intervals. Calculate the sum of the values of all possible partitions of the sequence $$$a_1, a_2, \ldots, a_n$$$. As this number can be very large, it is sufficient to provide its remainder when divided by $$$10^9+7$$$.
The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) representing the length of the sequence.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^{18}$$$) representing the sequence.
The output should contain a single integer, which is the remainder when the sum of the values of all possible partitions of the given sequence is divided by $$$10^9+7$$$.
4 7 3 1 2
170
Possible partitions of the sequence are: