D. Xor Partitions
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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$$$.

Input

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.

Output

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$$$.

Example
Input
4
7 3 1 2
Output
170
Note

Possible partitions of the sequence are:

  • $$$[7, 3, 1, 2]$$$ – with a value of $$$7$$$,
  • $$$[7, 3], [1, 2]$$$ – with a value of $$$4 \cdot 3 = 12$$$,
  • $$$[7], [3, 1, 2]$$$ – with a value of $$$7 \cdot 0 = 0$$$,
  • $$$[7, 3, 1], [2]$$$ – with a value of $$$5 \cdot 2 = 10$$$,
  • $$$[7, 3], [1], [2]$$$ – with a value of $$$4 \cdot 1 \cdot 2 = 8$$$,
  • $$$[7], [3], [1, 2]$$$ – with a value of $$$7 \cdot 3 \cdot 3 = 63$$$,
  • $$$[7], [3, 1], [2]$$$ – with a value of $$$7 \cdot 2 \cdot 2 = 28$$$,
  • $$$[7], [3], [1], [2]$$$ – with a value of $$$7 \cdot 3 \cdot 1 \cdot 2 = 42$$$.
The sum of the values of the partitions is $$$7 + 12 + 0 + 10 + 8 + 63 + 28 + 42 = 170$$$.