题目描述

给出 $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$ 取模的值。

3
1 2 3

6

样例解释

我们有$(1\ XOR\ 2)+(1\ XOR\ 3)+(2\ 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

提示

• $2\ \leq\ N\ \leq\ 3\ \times\ 10^5$
• $0\ \leq\ A_i\ <\ 2^{60}$