题目描述

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

求 $\\sum_{i=1}^{N-1}\\sum_{j=i+1}^{N} (A_i \\text{异或} A_j)$，对 $(10^9+7)$ 取模。

什么是异或（XOR）？

整数 $A$ 和 $B$ 的异或，表示为 $A \\text{ XOR } B$，定义如下：

• 将 $A \\text{ XOR } B$ 转换成二进制形式后，第 $2^k$ ($k \\geq 0$) 位上的数字为 $1$ 当且仅当 $A$ 或 $B$ 的第 $2^k$ 位上的数字为 $1$，否则为 $0$。

例如，$3 \\text{ XOR } 5 = 6$。 （转换成二进制形式： $011 \\text{ XOR } 101 = 110$。）

约束条件

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

输入

从标准输入读取输入数据，其格式如下：

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

输出

将结果 $\\sum_{i=1}^{N-1}\\sum_{j=i+1}^{N} (A_i \\text{异或} A_j)$ 对 $(10^9+7)$ 取模后打印出来。

示例输入 1

3
1 2 3

示例输出 1

6

我们有 $(1\\text{异或} 2)+(1\\text{异或} 3)+(2\\text{异或} 3)=3+2+1=6$。

示例输入 2

10
3 1 4 1 5 9 2 6 5 3

示例输出 2

237

示例输入 3

10
3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820

示例输出 3

103715602

对结果取 $(10^9+7)$ 模后打印。