CF1466E Apollo versus Pan

只有少数人知道，Pan 和 Apollo 不仅仅在争夺最伟大音乐家的称号。几千年后，他们还在数学（或者说快速计算）方面相互挑战。他们要解决的任务如下： 给定 $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) $$ 其中，$\&$ 表示[按位与](https://en.wikipedia.org/wiki/Bitwise_operation#AND)，$|$ 表示[按位或](https://en.wikipedia.org/wiki/Bitwise_operation#OR)。 Pan 和 Apollo 可以在几秒钟内解决这个问题。你能做到吗？为了方便，请将答案对 $10^9 + 7$ 取模。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量，接下来是 $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$ 个测试用例的答案。

由 ChatGPT 4.1 翻译