#include <bits/stdc++.h>

#define ed end()
#define bg begin()
#define mp make_pair
#define pb push_back
#define all(x) x.bg,x.ed
#define newline puts("")
#define si(x) ((int)x.size())
#define rep(i,n) for(int i=1;i<=n;++i)
#define rrep(i,n) for(int i=0;i<n;++i)
#define srep(i,s,t) for(int i=s;i<=t;++i)
#define drep(i,s,t) for(int i=t;i>=s;--i)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int Maxn = 5e5+10;
const int Inf = 0x7f7f7f7f;
const ll Inf_ll = 1ll*Inf*Inf;
const int Mod = 1e9+7;
const double eps = 1e-7;

int n, num[66];
ll a[Maxn];

void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)  scanf("%lld",&a[i]);
    ll ans = 0;
    for(int j=0;j<=60;j++)  num[j] = 0;
    for(int i=1;i<=n;i++)  for(int j=0;j<=60;j++)
        if( a[i]&(1ll<<j) )  num[j]++;
    
    for(int i=1;i<=n;i++)
    {
        ll t1 = 0, t2 = 0;
        for(int j=0;j<=60;j++)  if( a[i]&(1ll<<j) )
            t1 = (t1 + (1ll<<j)%Mod*num[j]%Mod)%Mod;
        for(int j=0;j<=60;j++)
        {
            if( a[i]&(1ll<<j) )
                t2 = (t2 + (1ll<<j)%Mod*n%Mod)%Mod;
            else 
                t2 = (t2 + (1ll<<j)%Mod*num[j]%Mod)%Mod;
        }
        ans = (ans + t1*t2%Mod)%Mod;
    }
    printf("%lld\n", ans);
    return ;
}

int main(){
    int T;
    scanf("%d",&T);
    for(int _=1;_<=T;_++)
    {
        solve();
    }
    return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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, …, x_n be the sequence of n non-negative integers. Find this value: $$$∑_{i=1}^n ∑_{j=1}^n ∑_{k=1}^n (x_i   \&   x_j) ⋅ (x_j   |   x_k)$$$

Here \& denotes the [bitwise and,](https://en.wikipedia.org/wiki/Bitwise_operation#AND) and | denotes the [bitwise or.](https://en.wikipedia.org/wiki/Bitwise_operation#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 ≤ t ≤ 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 ≤ n ≤ 5 ⋅ 10^5), the length of the sequence. The second one contains n non-negative integers x_1, x_2, …, x_n (0 ≤ x_i < 2^{60}), elements of the sequence.

The sum of n over all test cases will not exceed 5 ⋅ 10^5.

Output

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

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


Output


128
91
1600
505
0
1
502811676
264880351

### Response

```cpp
#include <bits/stdc++.h>

#define ed end()
#define bg begin()
#define mp make_pair
#define pb push_back
#define all(x) x.bg,x.ed
#define newline puts("")
#define si(x) ((int)x.size())
#define rep(i,n) for(int i=1;i<=n;++i)
#define rrep(i,n) for(int i=0;i<n;++i)
#define srep(i,s,t) for(int i=s;i<=t;++i)
#define drep(i,s,t) for(int i=t;i>=s;--i)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int Maxn = 5e5+10;
const int Inf = 0x7f7f7f7f;
const ll Inf_ll = 1ll*Inf*Inf;
const int Mod = 1e9+7;
const double eps = 1e-7;

int n, num[66];
ll a[Maxn];

void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)  scanf("%lld",&a[i]);
    ll ans = 0;
    for(int j=0;j<=60;j++)  num[j] = 0;
    for(int i=1;i<=n;i++)  for(int j=0;j<=60;j++)
        if( a[i]&(1ll<<j) )  num[j]++;
    
    for(int i=1;i<=n;i++)
    {
        ll t1 = 0, t2 = 0;
        for(int j=0;j<=60;j++)  if( a[i]&(1ll<<j) )
            t1 = (t1 + (1ll<<j)%Mod*num[j]%Mod)%Mod;
        for(int j=0;j<=60;j++)
        {
            if( a[i]&(1ll<<j) )
                t2 = (t2 + (1ll<<j)%Mod*n%Mod)%Mod;
            else 
                t2 = (t2 + (1ll<<j)%Mod*num[j]%Mod)%Mod;
        }
        ans = (ans + t1*t2%Mod)%Mod;
    }
    printf("%lld\n", ans);
    return ;
}

int main(){
    int T;
    scanf("%d",&T);
    for(int _=1;_<=T;_++)
    {
        solve();
    }
    return 0;
}
```