100 atcoder#ABC147D. [ABC147D] Xor Sum 4

[ABC147D] Xor Sum 4

Score : 400400 points

Problem Statement

We have NN integers. The ii-th integer is AiA_i.

Find $\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \text{ XOR } A_j)$, modulo (109+7)(10^9+7).

What is $\text{ XOR }$?

The XOR of integers AA and BB, A XOR BA \text{ XOR } B, is defined as follows:

  • When A XOR BA \text{ XOR } B is written in base two, the digit in the 2k2^k's place (k0k \geq 0) is 11 if either AA or BB, but not both, has 11 in the 2k2^k's place, and 00 otherwise.

For example, 3 XOR 5=63 \text{ XOR } 5 = 6. (In base two: 011 XOR 101=110011 \text{ XOR } 101 = 110.)

Constraints

  • 2N3×1052 \leq N \leq 3 \times 10^5
  • 0Ai<2600 \leq A_i < 2^{60}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

NN

A1A_1 A2A_2 ...... ANA_N

Output

Print the value $\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \text{ XOR } A_j)$, modulo (109+7)(10^9+7).

3
1 2 3
6

We have $(1\text{ XOR } 2)+(1\text{ XOR } 3)+(2\text{ XOR } 3)=3+2+1=6$.

10
3 1 4 1 5 9 2 6 5 3
237
10
3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820
103715602

Print the sum modulo (109+7)(10^9+7).