B. 异或计算

传统题

2000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Description

给定 $n$ 长非负整数数组 $a$ ，要求计算：

$$E = \sum_{i_1 = 1}^{n} \sum_{i_2 = 1}^{n} ...\sum_{i_n = 1}^{n} (a_{i_1} \oplus a_{i_2} \oplus .... \oplus a_{i_n} )$$

例如:

当 $n = 2$ 时，$E = \sum_{i_1 = 1}^{2} \sum_{i_2 = 1}^{2} (a_{i_1} \oplus a_{i_2}) = a_1 \oplus a_1 + a_1 \oplus a_2 + a_2 \oplus a_1 + a_2 \oplus a_2$.

第一行输入一个正整数 $n (1 \le n \le 10^6)$

第二行输入 $n$ 个非负整数，依次代表 $a_1,a_2,...,a_n (1 \le a_i \le 10^9)$ 。

输出 $E$ 对 $P$ 取模的结果，即 $E$ % $P,$ 其中 $P = 1000000007$ .

输入 # 1

3
3 1 3

输出 # 1