CF1466E.Apollo versus Pan

Only a few know that Pan and Apollo weren't only battling for the title of the GOAT musician. A few millenniums later, they also challenged each other in math (or rather in fast calculations). The task they got to solve is the following:

Let $x_1, x_2, \ldots, x_n$ be the sequence of $n$ non-negative integers. Find this value: $$\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n (x_i \, \& \, x_j) \cdot (x_j \, | \, x_k)$$

Here $\&$ denotes the bitwise and, and $|$ denotes the bitwise or.

Pan and Apollo could solve this in a few seconds. Can you do it too? For convenience, find the answer modulo $10^9 + 7$.

只有少数人知道，潘和阿波罗不仅为“史上最伟大音乐家”的头衔而战。几千年后，他们还在数学（或者说快速计算）领域一较高下。他们需要解决的问题如下：

设 $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)$$

其中 $\&$ 表示按位与运算，$|$ 表示按位或运算。

潘和阿波罗能在几秒钟内解出此题。你也能做到吗？为方便起见，请将答案对 $10^9 + 7$ 取模。

The first line of the input contains a single integer $t$ ($1 \leq t \leq 1\,000$) denoting the number of test cases, then $t$ test cases follow.

The first line of each test case consists of a single integer $n$ ($1 \leq n \leq 5 \cdot 10^5$), the length of the sequence. The second one contains $n$ non-negative integers $x_1, x_2, \ldots, x_n$ ($0 \leq x_i \lt 2^{60}$), elements of the sequence.

The sum of $n$ over all test cases will not exceed $5 \cdot 10^5$.

输入的第一行包含一个整数 $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 \lt 2^{60}$），即该序列的元素。

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

Print $t$ lines. The $i$-th line should contain the answer to the $i$-th text case.

输出 $t$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案。