#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
typedef long long llint;

const int N = 500000;
const int M = 60;
const int MOD = 1000000007;
int n;
llint x[N];
int b1cnt[M];
int b1s[N][M + 1];
int b0s[N][M + 1];
llint s1bs[N];

void readin() {
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> x[i];
  }
}

void solve() {
  memset(b1cnt, 0, sizeof(b1cnt));
  for (int i = 0; i < n; ++i) {
    b1s[i][0] = 0;
    b0s[i][0] = 0;
    s1bs[i] = 0;
    for (int j = 0; j < M; ++j) {
      if ((x[i] & (1LL << j)) != 0) {
        ++b1cnt[j];
        b1s[i][++b1s[i][0]] = j;
        s1bs[i] += (1LL << j) % MOD;
        s1bs[i] %= MOD;
      } else {
        b0s[i][++b0s[i][0]] = j;
      }
    }
  }
  llint res = 0;
  llint p, q;
  for (int i = 0; i < n; ++i) {
    p = 0;
    for (int j_ = 1; j_ <= b1s[i][0]; ++j_) {
      int j = b1s[i][j_];
      llint tmp = (1LL << j) % MOD;
      tmp *= b1cnt[j];
      tmp %= MOD;
      p += tmp;
      p %= MOD;
    }
    for (int k_ = 1; k_ <= b0s[i][0]; ++k_) {
      int k = b0s[i][k_];
      q = p;
      q *= (1LL << k) % MOD;
      q %= MOD;
      q *= b1cnt[k];
      q %= MOD;
      res += q;
      res %= MOD;
    }
    q = p;
    q *= s1bs[i];
    q %= MOD;
    q *= n;
    q %= MOD;
    res += q;
    res %= MOD;
  }
  cout << res << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  int tc;
  cin >> tc;
  while (tc--) {
    readin();
    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 <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
typedef long long llint;

const int N = 500000;
const int M = 60;
const int MOD = 1000000007;
int n;
llint x[N];
int b1cnt[M];
int b1s[N][M + 1];
int b0s[N][M + 1];
llint s1bs[N];

void readin() {
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> x[i];
  }
}

void solve() {
  memset(b1cnt, 0, sizeof(b1cnt));
  for (int i = 0; i < n; ++i) {
    b1s[i][0] = 0;
    b0s[i][0] = 0;
    s1bs[i] = 0;
    for (int j = 0; j < M; ++j) {
      if ((x[i] & (1LL << j)) != 0) {
        ++b1cnt[j];
        b1s[i][++b1s[i][0]] = j;
        s1bs[i] += (1LL << j) % MOD;
        s1bs[i] %= MOD;
      } else {
        b0s[i][++b0s[i][0]] = j;
      }
    }
  }
  llint res = 0;
  llint p, q;
  for (int i = 0; i < n; ++i) {
    p = 0;
    for (int j_ = 1; j_ <= b1s[i][0]; ++j_) {
      int j = b1s[i][j_];
      llint tmp = (1LL << j) % MOD;
      tmp *= b1cnt[j];
      tmp %= MOD;
      p += tmp;
      p %= MOD;
    }
    for (int k_ = 1; k_ <= b0s[i][0]; ++k_) {
      int k = b0s[i][k_];
      q = p;
      q *= (1LL << k) % MOD;
      q %= MOD;
      q *= b1cnt[k];
      q %= MOD;
      res += q;
      res %= MOD;
    }
    q = p;
    q *= s1bs[i];
    q %= MOD;
    q *= n;
    q %= MOD;
    res += q;
    res %= MOD;
  }
  cout << res << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  int tc;
  cin >> tc;
  while (tc--) {
    readin();
    solve();
  }
  return 0;
}

```