J1 实践-4 异或运算

题目描述

给出有 $N$ 个元素的序列，其值依次为 $A_1,A_2, ...,A_N$ 。

请求出 $\sum\limits^{N-1}_{i=1}\sum\limits^{N}_{j=i+1}(A_i~\oplus~A_j)$ 的值（ $\oplus$ 为异或运算符），结果可能会很大，输出 $\text{mod}~10^9+7$ 后的结果。

输入格式

共两行：

第一行一个整数 $N$ ，表示序列元素的数量；

第二行 $N$ 个整数 $A_i$ ，表示第 $i$ 个元素的值。

输出格式

一行一个整数，输出模$10^9+7$ 后 $\sum\limits^{N-1}_{i=1}\sum\limits^{N}_{j=i+1}(A_i~\oplus~A_j)$ 的值。

样例输入1

3
1 2 3

样例输出1

6

样例1解析

$(1\oplus 2)+(1\oplus 3)+(2\oplus 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

数据范围

对于 $100 \%$ 的数据：$2\leq N \leq 3\times 10^5, 0\leq A_i\leq 2^{60}$ 。