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

题目描述

徐老师有一个包含 $n$ 个数字的序列，分别为 $a_1,a_2,a_3 \dots a_n$

现在徐老师随意选出一对数字 $a_i$ 和 $a_j$，其中 $i < j$

徐老师认为这对数字的价值是 $max(a_i,a_j) * (a_i \& a_j)$

而现在徐老师提出了一个简单的问题，请问这个序列中所有合法数对的价值总和是多少？

P.S.1 $max(x,y)$ 表示取 $x,y$ 中大的数字 P.S.2 $\&$ 表示位运算中的与操作

输入格式

输入第一行是一个整数 $n$，表示徐老师的序列数字个数

输入第二行是 $n$ 个整数，用空格隔开，依次表示每个数字

输出格式

输出一行，包含一个整数，表示价值总和，答案对 $1e9+7$ 取模

数据范围

对于 $20\%$ 的数据，保证 $1 \leq n \leq 3000, 0 \leq a_i \leq 2^{30}$

对于 $50\%$ 的数据，保证 $1 \leq n \leq 100000, 0 \leq a_i \leq 2^{12}$

对于 $100\%$ 的数据，保证 $1 \leq n \leq 100000, 0 \leq a_i \leq 2^{30}$

样例输入1

3
3 1 2

样例输出1

9

样例输入2

5
1 2 3 4 5

样例输出2

39