思路：拆位
这里下标从 0 开始。
首先考虑两个元素对 ai,aj(i<j)，在 (i+1)×(n−j) 个子数组中有贡献，最终我们是将所有异或和都加起来。
我们对于两个数异或值的每个二进制位单独来考虑。
枚举 ai，对于 ai 的第 k 个二进制位，对于答案有贡献，必然是
aj 的第 k 个二进制位与其异或值为 1 ，那么就是 a(i,k)=0,a(j,k)=1 或者 a(i,k)=1,a(j,k)=0 的情况 。
题目描述
小美有一个长度为 n 的数组 a 。
他对一个数组的权值定义为，这个数组中两个不同的不同下标 i,j(0≤i<j<n) ，所有 ai xor aj 的和。
即 $\sum\limits_{i=0}^{n-2}\sum\limits_{j=i+1}^{n-1} a_i\ xor\ a_j$ 。
现在小美想要问你，这个数组的所有连续子数组的权值之和是多少。
输入描述
第一行，一个整数 n(1≤n≤105)，表示数组的长度。
第二行，n 个整数，第 i 个整数为 ai(1≤ai≤109) 。
输出描述
一个整数，表示所有子数组的权值之和，答案对 109+7 取模
样例
输入
3
1 2 3
输出
10
说明
对于子数组 a[1,2] 来说，权值为 3
对于子数组 a[2,3] 来说，权值为 1
对于子数组 a[1,2,3] 来说，权值为 6
3+1=6=10
