当前没有测试数据。

问题描述

xor是一种二进制位运算。运算规则如下： $0 \text{ xor } 0 = 0, 1 \text{ xor } 0 = 1, 0 \text{ xor } 1 = 1, 1 \text{ xor } 1 = 0$

对于任意两个数的xor运算规则，将他们写成$2$进制形式，逐位计算xor值。

如 $5 \text{ xor } 6$，写成二进制可以看成$101 \text{ xor } 110$，每一位分别xor，得到二进制结果$011$，也就是数字$3$。所以 $5 \text{ xor } 6 = 3$。

给你 $n$ 个数 $a_1, a_2, \dots, a_n$，求任意两个数xor的结果的和。也就是求：

$$\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} a_i \text{ xor } a_j $$

对 $10^9 + 7$ 取模的值。

输入格式

第一行为一个正整数 $n$。 第二行有 $n$ 个整数 $a_i$。

输出格式

输出答案。

输入输出样例

样例输入 #1

3
1 2 3

样例输出 #1

6

样例1解释： $1 \text{ xor } 2 + 1 \text{ xor } 3 + 2 \text{ xor } 3 = 3 + 2 + 1 = 6$

---

样例输入 #2

5
1 0 1 1 0

样例输出 #2

6

---

样例输入 #3

8
1 11 111 1111 11111 111111 1111111 11111111

样例输出 #3

86023886

说明/提示

对于$100$的数据， $2 \le n \le 3 \times 10^5$。 $0 \le a_i \le 2^{60}$。