#include <iostream>

using namespace std;
using ll = long long;

constexpr int MAXN = 500000;
constexpr int MAXB = 60;
constexpr ll  MODN = 1000000007;

// Values
ll a[MAXN];

// Counts of bits
ll b[MAXB];

// Sum of this bit over all elements
ll bs[MAXB];

// Sum of all elements ANDed with this value
ll vs[MAXN];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int t;
  cin >> t;

  for(int q = 0; q < t; ++ q) {
    int n;
    cin >> n;

    for(int i = 0; i < MAXB; ++ i) {
      b[i] = bs[i] = 0;
    }
    
    for(int i = 0; i < n; ++ i) {
      ll v;
      cin >> v;
      a[i] = v;
      for(int bc = 0; bc < MAXB; ++ bc) {
        if(v & (1ll << bc)) {
          ++ b[bc];
          bs[bc] += (1ll << bc) % MODN;
          bs[bc] %= MODN;
        }
      }
    }

    // Sum of all the values ANDed with another value
    ll sumA = 0;
    for(int i = 0; i < n; ++ i) {
      // Select this value as the mask
      ll v = a[i];
      vs[i] = 0;
      // For each set bit in v
      for(int bi = 0; bi < MAXB; ++ bi) {
        if(v & (1ll << bi)) {
          // Add the sum of that bit
          vs[i] += bs[bi];
          vs[i] %= MODN;
        }
      }
      sumA += vs[i];
      sumA %= MODN;
    }
    
    ll sum = 0;
    // For each bit (in the or part)
    for(int bc = 0; bc < MAXB; ++ bc) {
      // For each value x_j containing that bit
      for(int i = 0; i < n; ++ i) {
        ll v = a[i];
        if(v & (1ll << bc)) {
          // Find the sum of all values and'ed with that value
          // == the sum of sums of values for the bits in x_j
          ll cs = vs[i];

          // This sum occurs n - b[bc] times
          // (once for all x_k which don't have this bit set)
          cs *= (n - b[bc]);
          cs %= MODN;
          
          // Multiply by this bit and add to the sum
          sum += (cs * ((1ll << bc) % MODN)) % MODN;
          sum %= MODN;
        }
      }
      // For each x_k containing that bit, the sum of all values ANDed with
      // each element is obtained; multiply that with the bit
      // (x_i and x_j can be chosen freely)
      sum += ((sumA * b[bc]) % MODN) * ((1ll << bc) % MODN) % MODN;
      sum %= MODN;
    }

    cout << sum << '\n';
  }
}

### Prompt

In Cpp, your task is to solve 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 <iostream>

using namespace std;
using ll = long long;

constexpr int MAXN = 500000;
constexpr int MAXB = 60;
constexpr ll  MODN = 1000000007;

// Values
ll a[MAXN];

// Counts of bits
ll b[MAXB];

// Sum of this bit over all elements
ll bs[MAXB];

// Sum of all elements ANDed with this value
ll vs[MAXN];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int t;
  cin >> t;

  for(int q = 0; q < t; ++ q) {
    int n;
    cin >> n;

    for(int i = 0; i < MAXB; ++ i) {
      b[i] = bs[i] = 0;
    }
    
    for(int i = 0; i < n; ++ i) {
      ll v;
      cin >> v;
      a[i] = v;
      for(int bc = 0; bc < MAXB; ++ bc) {
        if(v & (1ll << bc)) {
          ++ b[bc];
          bs[bc] += (1ll << bc) % MODN;
          bs[bc] %= MODN;
        }
      }
    }

    // Sum of all the values ANDed with another value
    ll sumA = 0;
    for(int i = 0; i < n; ++ i) {
      // Select this value as the mask
      ll v = a[i];
      vs[i] = 0;
      // For each set bit in v
      for(int bi = 0; bi < MAXB; ++ bi) {
        if(v & (1ll << bi)) {
          // Add the sum of that bit
          vs[i] += bs[bi];
          vs[i] %= MODN;
        }
      }
      sumA += vs[i];
      sumA %= MODN;
    }
    
    ll sum = 0;
    // For each bit (in the or part)
    for(int bc = 0; bc < MAXB; ++ bc) {
      // For each value x_j containing that bit
      for(int i = 0; i < n; ++ i) {
        ll v = a[i];
        if(v & (1ll << bc)) {
          // Find the sum of all values and'ed with that value
          // == the sum of sums of values for the bits in x_j
          ll cs = vs[i];

          // This sum occurs n - b[bc] times
          // (once for all x_k which don't have this bit set)
          cs *= (n - b[bc]);
          cs %= MODN;
          
          // Multiply by this bit and add to the sum
          sum += (cs * ((1ll << bc) % MODN)) % MODN;
          sum %= MODN;
        }
      }
      // For each x_k containing that bit, the sum of all values ANDed with
      // each element is obtained; multiply that with the bit
      // (x_i and x_j can be chosen freely)
      sum += ((sumA * b[bc]) % MODN) * ((1ll << bc) % MODN) % MODN;
      sum %= MODN;
    }

    cout << sum << '\n';
  }
}

```