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

题目背景

大维在课堂上提出了一个有趣的编程问题：给定一个非负整数序列，希望你分析下面这段朴素枚举两两组合的代码，计算最终累加值并输出。

题目描述

现在，你手里有一个长度为 n 的非负整数序列

下面给出一段代码：

ans = 0;
for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++)
        ans += max(a[i], a[j]) * (a[i] & a[j]);

其中，max(a[i], a[j]) 表示 $a_i$ 和 $a_j$ 中的较大值，& 表示二进制下的按位与运算。

你的任务是计算给定序列下，变量 ans 的最终值，并输出 ans 对 $10^9+7$ 取模后的结果。由于直接套用上述双重循环在最坏情况下无法通过时间限制，请注意挖掘数据的位运算性质以设计更高效的算法。

输入格式

第一行一个正整数 n，表示序列长度。
第二行 n 个非负整数，第 i 个数即为 $a_i$。

输出格式

输出一个整数，表示 ans mod (10^9+7) 的值。

样例

5
1 2 3 4 5

39

样例解释

对于序列 [1,2,3,4,5]，枚举所有 $1 \le i < j \le 5$，计算

数据范围

• 对于 20% 的数据，$1 \le n \le 3000$, $0 \le a_i < 2^{30}$.
• 对于 50% 的数据，$1 \le n \le 10^5$, $0 \le a_i < 2^{12}$.
• 对于 100% 的数据，$1 \le n \le 10^5$, $0 \le a_i < 2^{30}$.

附件