1439: 小V的lowbit

这天，小V在学习lowbit。

lowbit(x)的意思是将 x 分解成二进制，它的值就是$2^k$，

其中 k 是最小的满足(x & $2^k$)>0 的数。（&是二进制中的 and 运算）

小V甚至知道 lowbit(x)=(x&-x)。但这并没什么用处。

现在小V 有了 n 个数字，为了使自己更好的理解 lowbit 是什么意思。

它想对所有 $n^2$ 个二元组求 lowbit。

具体的，对于一个二元组(ai,aj)，它的值为 lowbit(ai xor aj) (xor 表示异或的意思，在程序中我们可用ai^aj来计算ai xor aj）

例如 5的二进制表示为101，2的二进制表示为10，我们可以得到 5 xor 2 = $(111)_2$ = 7

(对数的每一个二进制位进行比较，若不同，则该位为1，若相同，则该位为0，即1 xor 0 =1, 0 xor 1 =1 , 0 xor 0 =0, 1 xor 1 =0)

那么总共有 $n^2$ 对二元组，小V想知道所有二元组的值加起来是多少。

这个答案可能很大，你只需输出这个值对 1000000007 取模后的结果就可以了。

第一行一个数 n，表示有 n 个这样的数字。

第二行 n 个数 ai

一个数表示答案。

5

1 2 3 4 5

32

对于 30%的数据 n<=1000。

对于另外 10%的数据 ai<=1。

对于再另外 10%的数据 ai<=3。

对于再再另外 20%的数据 ai<1024。

对于 100%的数据 1<=n<=100000,0<=ai<2^30。

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！