Apollo versus Pan
Contest: Good Bye 2020
Difficulty rating: 1800
Tags: bitmasks, brute force, math

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

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
128
91
1600
505
0
1
502811676
264880351

Editorial:
The formula given in this task looks difficult to calculate, so we can rewrite it: $$$$$$ \sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n (x_i \, \& \, x_j) \cdot (x_j \, | \, x_k) = \sum_{j=1}^n \sum_{i=1}^n (x_i \, \& \, x_j) \sum_{k=1}^n (x_j \, | \, x_k) = \sum_{j=1}^n \left[ \sum_{i=1}^n (x_i \, \& \, x_j) \right] \cdot \left[ \sum_{k=1}^n (x_j \, | \, x_k) \right] $$$$$$
We fix the element $$$x_j$$$. Now the task is to calculate two sums $$$\sum_i (x_i \, \& \, x_j)$$$ and $$$\sum_k (x_j \, | \, x_k)$$$, and multiply them by each other.
Let's define function $$$f(x, c)$$$ as the value of $$$c$$$-th bit in $$$x$$$. For example $$$f(13, 1) = 0$$$, because $$$13 = 11\underline{0}1_2$$$, and $$$f(12, 2) = 1$$$, because $$$12 = 1\underline{1}00_2$$$. Additionally, define $$$M$$$ as the smallest integer such that $$$\forall_i \, x_i < 2^M$$$. Note that in this task $$$M \leq 60$$$.
We can rewrite our sums using function $$$f$$$: $$$$$$ \sum_i (x_i \, \& \, x_j) = \sum_{c = 0}^{M} 2^c \sum_i f(x_i, c) \cdot f(x_j, c) = \sum_{c = 0}^{M} 2^c f(x_j, c) \sum_i f(x_i, c) $$$$$$ $$$$$$ \sum_k (x_j \, | \, x_k) = \sum_{c = 0}^{M} 2^c \sum_k 1 - (1 - f(x_j, c)) \cdot (1 - f(x_k, c)) = \sum_{c = 0}^{M} 2^c \left[ n - (1 - f(x_j, c)) \sum_k (1 - f(x_k, c)) \right] $$$$$$
In other words, we just split elements $$$x_i, x_j, x_k$$$ into the powers of two.
If we memorize the values of $$$\sum_i f(x_i, c)$$$, for each $$$c \in \{0, 1, \ldots, M \}$$$, then we can calculate the desired sums in $$$\mathcal{O}(M)$$$ for fixed $$$x_j$$$ using the above equations.
So the final solution is to iterate over all elements in the array and fix them as $$$x_j$$$, and sum all of the results obtained. Complexity is $$$\mathcal{O}(nM) = \mathcal{O}(n \log \max_i(x_i))$$$