当前没有测试数据。

3.lowbit 求和

题目描述

给定数列$A$，求下式的值：

$$\sum_{i=1}^{n}\sum_{j=1}^{n}\text{lowbit}(A_i \oplus A_j) $$

其中，$\text{lowbit}(x) = x \ \text{and} \ (-x)$。

输入格式

第一行一个整数$n$。

接下来一行$n$个整数，表示数列$A$。

输出格式

一个整数表示答案，由于答案很大，请你输出答案对$199907210507$取模后的值。

数据范围与提示

对于$100\%$的数据，$1 < n < 100000$，$0 \leq A_i \leq 2^{60} - 1$。

本题采用子任务捆绑测试。对于每个子任务，你只有通过了这个子任务的所有数据，才能获得这个子任务的分数。

• 子任务$1$（$20$分）：$1 < n < 100$，$0 \leq A_i \leq 2^{60} - 1$。
• 子任务$2$（$20$分）：$1 < n < 100000$，$0 \leq A_i \leq 2^{10} - 1$。
• 子任务$3$（$60$分）：无特殊限制。

样例

5
1 2 3 4 5

32