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