题目描述

给定一个长度为n的数组a。

请求解：

\sum_{i=1}^{n}\sum_{j=i + 1}^{n}(a_i \oplus a_j)

结果对10^9+7取模。

输入描述

第一行一个整数n表示数组大小。(1 \le n \le 10^5)

第二行n个整数表示数组a。(1 \le a_i \le 10^9)

输出描述

一行一个整数表示结果。

输入样例1

3
1 2 5

输出样例1

14

解释

(1 \oplus 2) + (1 \oplus 5) + (2 \oplus 5) = 14