异或和

题目描述

有 $N$ 个整数，第 $i$ 个整数是 $A_i$。

求 $\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \text{ XOR } A_j)$ 除以 $10^9+7$ 的余数。

什么是 $\text{ XOR }$

整数 $A, B$ 的按位异或 $a \text{ XOR } b$ 定义如下。

• 将 $a \text{ XOR } b$ 用二进制表示时，$2^k$（$k \geq 0$）位上的数字是：当 $A, B$ 用二进制表示时的 $2^k$ 位上的数字恰好只有一方为 $1$ 时为 $1$，否则为 $0$。

例如，$3 \text{ XOR } 5 = 6$（用二进制表示：$011 \text{ XOR } 101 = 110$）。

输入格式

输入按以下格式从标准输入给出：

$N$
$A_1$ $A_2$ $...$ $A_N$

输出格式

输出 $\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \text{ XOR } A_j)$ 除以 $10^9+7$ 的余数。

样例

3
1 2 3

6

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

请输出和除以 $10^9+7$ 的余数。

数据范围

• $2 \leq N \leq 3 \times 10^5$
• $0 \leq A_i \lt 2^{60}$
• 输入中的所有值均为整数。