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

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

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

见题面 Input 部分

见题面 Output 部分