Renovation Pricing Simulation

Mr. Wang is planning to renovate his house and contacts a decoration company. The company uses an automatic quotation system. The system accepts N renovation costs: \(A_1, A_2, \dots, A_N\). Internally, between every two adjacent numbers, the system inserts one of three operators: \(+\), \(-\) or \(\oplus\) (bitwise XOR). It then evaluates the resulting expression using a special operator priority: the XOR operation \((\oplus)\) has the highest precedence, while addition and subtraction come afterward.

For example, in the expression:

\(A_1 \oplus A_2 + A_3\) is evaluated as \((A_1 \oplus A_2) + A_3\), whereas
\(A_1 + A_2 \oplus A_3\) is evaluated as \(A_1 + (A_2 \oplus A_3)\).

Mr. Wang is skeptical about the final quote provided by the system. To verify its correctness, he plans to simulate the system by considering every possible combination of operators inserted between the given numbers, computing the result for each combination, and then summing up all these results. Since the total number of combinations might be huge, you are only required to output the sum modulo \(10^9+7\).

Note: There are exactly three choices for each of the \(N-1\) operator positions.

inputFormat

The first line contains an integer \(N\) representing the number of renovation cost items. The second line contains \(N\) space-separated integers \(A_1, A_2, \dots, A_N\).

outputFormat

Output a single integer: the sum of the values of all possible expressions, modulo \(10^9+7\).

sample

2
1 2

5