题目描述

$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$ で割った余りを出力せよ。

题目大意

题目描述

给出 $n$ 个整数 $a_i$，请求出 $\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(a_i \operatorname{xor}a_j)$ 对 $10^9 + 7$ 取模的值。

输入格式

第一行为一个正整数 $n$。

第二行有 $n$ 个整数 $a_i$。

输出格式

输出 $\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(a_i \operatorname{xor}a_j)$ 对 $10^9 + 7$ 取模的值。

数据范围

$2 \le n \le 3 \times 10 ^ 5, 0 \le a_i \le 2^{60}$。

3
1 2 3

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

提示

制約

• $2\ \leq\ N\ \leq\ 3\ \times\ 10^5$
• $0\ \leq\ A_i\ <\ 2^{60}$
• 入力中のすべての値は整数である。

Sample Explanation 1

$ (1\text{\ XOR\ }\ 2)+(1\text{\ XOR\ }\ 3)+(2\text{\ XOR\ }\ 3)=3+2+1=6 $ となります。

Sample Explanation 3

和を $10^9+7$ で割った余りを出力してください。