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$$$.

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 < 2^{60}$ ), elements of the sequence.

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

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