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.