Sum of XORs

Problem Description

You are given an array $a_1, a_2, \dots, a_n$ of length $n$. Compute the value of the following expression modulo $10^9 + 7$:

$$\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} (a_i \; \mathrm{XOR} \; a_j)$$

Input Format

The first line contains an integer $n$.

The next line contains $n$ integers $a_1, a_2, \dots, a_n$.

Output Format

Output one integer: the answer.

Sample Input

3
1 2 3

Sample Output

6

Constraints

$2 \leq n \leq 300000$, $0 \leq a_i < 2^{60}$.