#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define all(x) x.begin(),x.end()
#define pb emplace_back
#define pob pop_back()
#define ms0(s) memset(s,0,sizeof s)
#define ff first
#define ss second
typedef long long int ll;
#define vll vector<ll>
#define vpll vector<pair<ll,ll>>
#define vvll vector<vector<ll>>
#define pll pair<ll,ll>
#define prq priority_queue<ll>  //max-heap
#define psq priority_queue<ll,vector<ll>,greater<ll>>  //min-heap
#define m_p make_pair
#define vcc vector<char>
#define vss vector<string>
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define setbit(n) __builtin_popcountll(n)
const ll mxn = 0;
int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll t = 1;
	cin >> t;
	while (t--)
	{
		ll i, j, k, n, m = 0;
		cin >> n;
		vll x(n);
		vll p1(n), p2(n);
		ll bits[62];
		ms0(bits);
		for (i = 0; i < n; i++) {
			cin >> x[i];
			for (j = 0; j < 60; j++)
				if ((1LL << j)&x[i])
					bits[j]++;
		}

		for (i = 0; i < n; i++)
		{
			p2[i] = ((n % mod) * (x[i] % mod)) % mod;
			for (j = 0; j < 60; j++)
				if (bits[j])
				{
					if (((1LL << j)&x[i]) == 0)
						(p2[i] += (bits[j] % mod) * ((1LL << j) % mod)) %= mod;
				}
		}
		for (i = 0; i < n; i++)
		{
			p1[i] = x[i];
			for (j = 0; j < 60; j++)
				if ((x[i] & (1LL << j)))
				{
					(p1[i] += ((bits[j] - 1) % mod) * ((1LL << j) % mod)) %= mod;
				}
		}
		ll ans = 0;
		for (i = 0; i < n; i++)
		{
			(ans += p1[i] % mod * p2[i] % mod) %= mod;
		}
		cout  << ans << "\n";;
	}
	return 0;
}
### Prompt

Please provide a Cpp coded solution to the problem described below:

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>
using namespace std;
#define mod 1000000007
#define all(x) x.begin(),x.end()
#define pb emplace_back
#define pob pop_back()
#define ms0(s) memset(s,0,sizeof s)
#define ff first
#define ss second
typedef long long int ll;
#define vll vector<ll>
#define vpll vector<pair<ll,ll>>
#define vvll vector<vector<ll>>
#define pll pair<ll,ll>
#define prq priority_queue<ll>  //max-heap
#define psq priority_queue<ll,vector<ll>,greater<ll>>  //min-heap
#define m_p make_pair
#define vcc vector<char>
#define vss vector<string>
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define setbit(n) __builtin_popcountll(n)
const ll mxn = 0;
int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll t = 1;
	cin >> t;
	while (t--)
	{
		ll i, j, k, n, m = 0;
		cin >> n;
		vll x(n);
		vll p1(n), p2(n);
		ll bits[62];
		ms0(bits);
		for (i = 0; i < n; i++) {
			cin >> x[i];
			for (j = 0; j < 60; j++)
				if ((1LL << j)&x[i])
					bits[j]++;
		}

		for (i = 0; i < n; i++)
		{
			p2[i] = ((n % mod) * (x[i] % mod)) % mod;
			for (j = 0; j < 60; j++)
				if (bits[j])
				{
					if (((1LL << j)&x[i]) == 0)
						(p2[i] += (bits[j] % mod) * ((1LL << j) % mod)) %= mod;
				}
		}
		for (i = 0; i < n; i++)
		{
			p1[i] = x[i];
			for (j = 0; j < 60; j++)
				if ((x[i] & (1LL << j)))
				{
					(p1[i] += ((bits[j] - 1) % mod) * ((1LL << j) % mod)) %= mod;
				}
		}
		ll ans = 0;
		for (i = 0; i < n; i++)
		{
			(ans += p1[i] % mod * p2[i] % mod) %= mod;
		}
		cout  << ans << "\n";;
	}
	return 0;
}
```