#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef double db;

typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef pair<db,db> pd;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<db> vd;
typedef vector<string> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

ll MOD = 1000000007;

// LATE :( RAJ SAAR IS PROOOOOOOOOOOOO

void RAJ_MEHTA_IS_PRO()
{
	int n;
	cin >> n;
	ll a[n];
	ll hashh[61] = {0};
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
		for(ll j = 0; j <= 60; j++) if((1ll << j) & a[i]) hashh[j] += 1;
	}
	ll sum = 0;
	for(int i = 0; i < n; i++)
	{
		ll sum1 = 0, sum2 = 0;
		for(ll j = 0; j <= 60; j++)
		{
			if((1ll << j) & a[i])
			{
				ll x = ((1ll << j) % MOD) * n;
				x %= MOD;
				if(x < 0) x += MOD;
				sum1 = (sum1 + x) % MOD;
//				cout << sum1 << " ======= " << x << "\n";
				ll y = ((1ll << j) % MOD) * hashh[j];
				y %= MOD;
				if(y < MOD) y += MOD;
				sum2 = (sum2 + y) % MOD;
//				cout << sum2 << " ======= " << y << "\n";
			}
			else
			{
				ll y = ((1ll << j) % MOD) * hashh[j];
				y %= MOD;
				if(y < MOD) y += MOD;
				sum1 = (sum1 + y) % MOD;
			}
//			cout << sum1 << " <<<==>>> " << sum2 << "\n";
		}
		sum = (sum + (sum1 * sum2) % MOD) % MOD;
	}
	cout << sum << "\n";
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin.exceptions(cin.failbit);
	cout.tie(NULL);
	int t = 1;
	cin >> t;
	while(t--)
	{
		RAJ_MEHTA_IS_PRO();
	}
	return 0;
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

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;

typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef double db;

typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef pair<db,db> pd;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<db> vd;
typedef vector<string> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

ll MOD = 1000000007;

// LATE :( RAJ SAAR IS PROOOOOOOOOOOOO

void RAJ_MEHTA_IS_PRO()
{
	int n;
	cin >> n;
	ll a[n];
	ll hashh[61] = {0};
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
		for(ll j = 0; j <= 60; j++) if((1ll << j) & a[i]) hashh[j] += 1;
	}
	ll sum = 0;
	for(int i = 0; i < n; i++)
	{
		ll sum1 = 0, sum2 = 0;
		for(ll j = 0; j <= 60; j++)
		{
			if((1ll << j) & a[i])
			{
				ll x = ((1ll << j) % MOD) * n;
				x %= MOD;
				if(x < 0) x += MOD;
				sum1 = (sum1 + x) % MOD;
//				cout << sum1 << " ======= " << x << "\n";
				ll y = ((1ll << j) % MOD) * hashh[j];
				y %= MOD;
				if(y < MOD) y += MOD;
				sum2 = (sum2 + y) % MOD;
//				cout << sum2 << " ======= " << y << "\n";
			}
			else
			{
				ll y = ((1ll << j) % MOD) * hashh[j];
				y %= MOD;
				if(y < MOD) y += MOD;
				sum1 = (sum1 + y) % MOD;
			}
//			cout << sum1 << " <<<==>>> " << sum2 << "\n";
		}
		sum = (sum + (sum1 * sum2) % MOD) % MOD;
	}
	cout << sum << "\n";
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin.exceptions(cin.failbit);
	cout.tie(NULL);
	int t = 1;
	cin >> t;
	while(t--)
	{
		RAJ_MEHTA_IS_PRO();
	}
	return 0;
}

```