← 返回题目列表

Codeforces · 1466/E

E. 阿波罗与潘

中文机器翻译题面 查看原题

只有少数人知道潘和阿波罗不仅仅是在争夺“山羊音乐家”的头衔。几千年后,他们还在数学(或者更确切地说是快速计算)方面相互挑战。他们要解决的任务如下:

令 $$$x_1, x_2, \ldots, x_n$$$ 为 $$$n$$$ 非负整数的序列。找到这个值: $$$$$$\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n (x_i \, \& \, x_j) \cdot (x_j \, | \, x_k)$$$$$$

这里$$$\&$$$表示按位与,$$$|$$$表示按位或。

Pan 和 Apollo 可以在几秒钟内解决这个问题。你也能做到吗?为方便起见,请以 $$$10^9 + 7$$$ 为模求出答案。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1\,000$$$) 表示测试用例的数量,然后是 $$$t$$$ 测试用例。

每个测试用例的第一行由一个整数 $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) 组成,即序列的长度。第二个包含 $$$n$$$ 非负整数 $$$x_1, x_2, \ldots, x_n$$$ ($$$0 \leq x_i < 2^{60}$$$),即序列的元素。

所有测试用例的 $$$n$$$ 总和不会超过 $$$5 \cdot 10^5$$$。

输出

打印 $$$t$$$ 行。第 $$$i$$$ 行应包含第 $$$i$$$ 文本案例的答案。

示例

输入 #1

8
2
1 7
3
1 2 4
4
5 5 5 5
5
6 2 2 1 0
1
0
1
1
6
1 12 123 1234 12345 123456
5
536870912 536870911 1152921504606846975 1152921504606846974 1152921504606846973

输出 #1

128
91
1600
505
0
1
502811676
264880351