思考

题目描述

给定一个长度为 $n$ 的非负整数序列 $a_1,a_2,\dots,a_n$，按照以下代码计算 ans 的值：

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 的值，并输出其对 $10^9+7$ 取模后的结果。

提示：直接套用上述代码无法通过满分数据，请注意挖掘性质。

输入格式

• 第一行一个正整数 $n$，表示序列的长度。
• 接下来一行 $n$ 个非负整数，依次表示序列的第 $1$ 个到第 $n$ 个数字。

输出格式

输出一行一个整数，表示 ans 对 $10^9+7$ 取模后的结果。

样例

输入

5
1 2 3 4 5

输出

39

数据规模与约定

共10组数据，每组数据点10分。

• 对于 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}$
• 模数：$10^9+7$