题目描述

给定长度为 \(n\) 的序列 \(a\)，求：

\[\sum_{i=1}^{n-1}\sum_{j=i+1}^n\max(a_i,a_j)\times(a_i\operatorname{xor}a_j+a_i\operatorname{or}a_j+a_i\operatorname{and}a_j)\bmod p\]

其中 \(p=10^9+7\)。

输入格式

第一行一个整数 \(n\)。

第二行 \(n\) 个整数，表示 \(a_i\)。

输出格式

一行一个整数表示答案。

样例

输入样例 #1

11
1 1 4 5 1 4 1 9 1 9 8 1 0

输出样例 #1

5624

输入样例 #2

7
11 45 14 19 19 81 0

输出样例 #2

121874

数据范围

\(1\leq n\leq 2\times 10^5\)，\(0\leq a_i<10^9+7\)