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$.

Input Format

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

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

Output Format

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

Sample

输入 # 1

3
3 1 3

输出 # 1

55