#ifdef _MSC_VER
#define _CRT_SECURE_NO_DEPRECATE
#pragma comment(linker, "/STACK:66777216")
#include <cstdio>
#define GETS gets_s
#else
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <stdio.h>
#define GETS gets
#endif
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <iostream>
#include <iterator>
#include <cmath>
#include <cstdlib>
#include <sstream>
#include <fstream>
#include <ctime>
#include <cstring>
#include <functional>
#include <chrono>
using namespace std;
#define pb push_back
#define ppb pop_back
#define pi 3.1415926535897932384626433832795028841971
#define mp make_pair
#define pii pair<int,int>
#define pdd pair<double,double>
#define INF 1000000000
#define FOR(i,a,b) for (int _n(b), i(a); i <= _n; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;i--)
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define rep(i,n) FOR(i,1,(n))
#define rept(i,n) FOR(i,0,(n)-1)
#define L(s) (int)((s).size())
#define C(a) memset((a),0,sizeof(a))
#define VI vector <int>
#define ll long long
#define MOD 1000000007

int a, b, c, d, n, m, k, kolt;
ll tmp;
ll mas[500002];
int co[62], co2[62][62], coz2[62][62];
int pc[128];

char buf[8388609], * ch = buf;
inline char get_char() {
	if (*ch == 0) {
		ch = buf;
		fread(buf, sizeof(char), 8388608, stdin);
	}
	return *(ch++);
}
inline void next_ll(ll& ans) {
	ans = 0;
	char ch;
	while ((ch = get_char()) < '0' || ch > '9');
	do {
		ans = ans * 10 + ch - '0';
	} while ((ch = get_char()) >= '0' && ch <= '9');
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	C(pc);
	pc[0] = 1;
	rep(i, 127) pc[i] = pc[i - 1] * 2 % MOD;

	next_ll(tmp);
	kolt = tmp;
	rep(hod, kolt) {
		next_ll(tmp);
		n = tmp;

		rept(i, n) {
			next_ll(mas[i]);
		}

		C(co); C(co2); C(coz2);

		rept(i, n) {
			rept(j, 60) {
				if (mas[i] & 1LL << j) {
					++co[j];

					rept(z, 60) {
						if (mas[i] & 1LL << z) {
							++co2[j][z];
						}
						else {
							++coz2[j][z];
						}
					}
				}
			}
		}

		int ans = 0;

		rept(x, 60) {
			rept(y, 60) {
				if (co2[x][y]) {
					int s1 = (ll)co2[x][y] * co[x] % MOD;
					ans = (ans + (ll)s1 * n % MOD * pc[x + y]) % MOD;
				}
				if (coz2[x][y]) {
					int s1 = (ll)coz2[x][y] * co[x] % MOD;
					ans = (ans + (ll)s1 * co[y] % MOD * pc[x + y]) % MOD;
				}
			}
		}

		printf("%d\n", ans);
	}
}

### Prompt

Please formulate 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
#ifdef _MSC_VER
#define _CRT_SECURE_NO_DEPRECATE
#pragma comment(linker, "/STACK:66777216")
#include <cstdio>
#define GETS gets_s
#else
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <stdio.h>
#define GETS gets
#endif
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <iostream>
#include <iterator>
#include <cmath>
#include <cstdlib>
#include <sstream>
#include <fstream>
#include <ctime>
#include <cstring>
#include <functional>
#include <chrono>
using namespace std;
#define pb push_back
#define ppb pop_back
#define pi 3.1415926535897932384626433832795028841971
#define mp make_pair
#define pii pair<int,int>
#define pdd pair<double,double>
#define INF 1000000000
#define FOR(i,a,b) for (int _n(b), i(a); i <= _n; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;i--)
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define rep(i,n) FOR(i,1,(n))
#define rept(i,n) FOR(i,0,(n)-1)
#define L(s) (int)((s).size())
#define C(a) memset((a),0,sizeof(a))
#define VI vector <int>
#define ll long long
#define MOD 1000000007

int a, b, c, d, n, m, k, kolt;
ll tmp;
ll mas[500002];
int co[62], co2[62][62], coz2[62][62];
int pc[128];

char buf[8388609], * ch = buf;
inline char get_char() {
	if (*ch == 0) {
		ch = buf;
		fread(buf, sizeof(char), 8388608, stdin);
	}
	return *(ch++);
}
inline void next_ll(ll& ans) {
	ans = 0;
	char ch;
	while ((ch = get_char()) < '0' || ch > '9');
	do {
		ans = ans * 10 + ch - '0';
	} while ((ch = get_char()) >= '0' && ch <= '9');
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	C(pc);
	pc[0] = 1;
	rep(i, 127) pc[i] = pc[i - 1] * 2 % MOD;

	next_ll(tmp);
	kolt = tmp;
	rep(hod, kolt) {
		next_ll(tmp);
		n = tmp;

		rept(i, n) {
			next_ll(mas[i]);
		}

		C(co); C(co2); C(coz2);

		rept(i, n) {
			rept(j, 60) {
				if (mas[i] & 1LL << j) {
					++co[j];

					rept(z, 60) {
						if (mas[i] & 1LL << z) {
							++co2[j][z];
						}
						else {
							++coz2[j][z];
						}
					}
				}
			}
		}

		int ans = 0;

		rept(x, 60) {
			rept(y, 60) {
				if (co2[x][y]) {
					int s1 = (ll)co2[x][y] * co[x] % MOD;
					ans = (ans + (ll)s1 * n % MOD * pc[x + y]) % MOD;
				}
				if (coz2[x][y]) {
					int s1 = (ll)coz2[x][y] * co[x] % MOD;
					ans = (ans + (ll)s1 * co[y] % MOD * pc[x + y]) % MOD;
				}
			}
		}

		printf("%d\n", ans);
	}
}

```