/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include "bits/stdc++.h"

#define rep(i,x,y) for(ll i=(x);i<(y);i++)
#define rrep(i,x,y) for(ll i=(ll)(y)-1;i>=(x);i--)
#define all(x) (x).begin(),(x).end()
#define itrout(x) for(int i=0;i<x.size();i++) {out << x[i] << (i==x.size()-1 ? "\n" : " ");}
#define debug(x) out << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#define debugbit(x, n) cerr << #x << " = " << bitset<n>(x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#define itrdebug(x) out << #x << " "; for (auto & el : (x)) {out << (el) << " ";} out << endl
//#define int long long

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

namespace mod {
    template <long long MOD>
    struct Int {
        long long x;
        Int(long long x = 0) : x((x % MOD + MOD) % MOD){}
        Int operator-() const { return Int<MOD>(-x);}
        Int& operator+=(const Int<MOD> a) {
            if ((x += a.x) >= MOD) x -= MOD;
            return *this;
        }
        Int& operator-=(const Int<MOD> a) {
            if ((x += MOD-a.x) >= MOD) x -= MOD;
            return *this;
        }
        Int& operator*=(const Int<MOD> a) {
            (x *= a.x) %= MOD; return *this;
        }
        Int operator+(const Int<MOD> a) const { return Int<MOD>(*this) += a;}
        Int operator-(const Int<MOD> a) const { return Int<MOD>(*this) -= a;}
        Int operator*(const Int<MOD> a) const { return Int<MOD>(*this) *= a;}
        Int pow(long long t) const {
            if (!t) return 1;
            Int<MOD> a = pow(t >> 1);
            a *= a;
            if (t&1) a *= *this;
            return a;
        }

        Int inv() const { return pow(MOD - 2);}
        Int& operator/=(const Int<MOD> a) { return *this *= a.inv();}
        Int operator/(const Int<MOD> a) const { return Int<MOD>(*this) /= a;}
    };
}
std::istream& operator>>(std::istream& is, const mod::Int<MOD>& a) { return is >> a.x;}
std::ostream& operator<<(std::ostream& os, const mod::Int<MOD>& a) { return os << a.x;}

class EApolloVersusPan {
public:
    void solve(std::istream& in, std::ostream& out) {
        int t;
        in >> t;
        vector<mod::Int<MOD>> pows(60);
        rep(pi,0,60) pows[pi] = mod::Int<MOD>(2).pow(pi);
        rep(ti,0,t) {
            int n;
            in >> n;
            vector<ll> x(n);
            rep(i,0,n) in >> x[i];
            mod::Int<MOD> answer;
            vector<int> cnt(60);
            rep(i,0,n) rep(j,0,60) {
                if (1LL << j & x[i]) ++cnt[j];
            }
            rep(i,0,n) {
                mod::Int<MOD> orsum, andsum;
                rep(j,0,60) {
                    if (1LL << j & x[i]) {
                        orsum += pows[j] * n;
                        andsum += pows[j] * cnt[j];
                    } else {
                        orsum += pows[j] * cnt[j];
                    }
                }
                answer += orsum * andsum;
            }
            out << answer << endl;
        }
    }
};


signed main() {
    EApolloVersusPan solver;
    std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	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
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include "bits/stdc++.h"

#define rep(i,x,y) for(ll i=(x);i<(y);i++)
#define rrep(i,x,y) for(ll i=(ll)(y)-1;i>=(x);i--)
#define all(x) (x).begin(),(x).end()
#define itrout(x) for(int i=0;i<x.size();i++) {out << x[i] << (i==x.size()-1 ? "\n" : " ");}
#define debug(x) out << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#define debugbit(x, n) cerr << #x << " = " << bitset<n>(x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#define itrdebug(x) out << #x << " "; for (auto & el : (x)) {out << (el) << " ";} out << endl
//#define int long long

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

namespace mod {
    template <long long MOD>
    struct Int {
        long long x;
        Int(long long x = 0) : x((x % MOD + MOD) % MOD){}
        Int operator-() const { return Int<MOD>(-x);}
        Int& operator+=(const Int<MOD> a) {
            if ((x += a.x) >= MOD) x -= MOD;
            return *this;
        }
        Int& operator-=(const Int<MOD> a) {
            if ((x += MOD-a.x) >= MOD) x -= MOD;
            return *this;
        }
        Int& operator*=(const Int<MOD> a) {
            (x *= a.x) %= MOD; return *this;
        }
        Int operator+(const Int<MOD> a) const { return Int<MOD>(*this) += a;}
        Int operator-(const Int<MOD> a) const { return Int<MOD>(*this) -= a;}
        Int operator*(const Int<MOD> a) const { return Int<MOD>(*this) *= a;}
        Int pow(long long t) const {
            if (!t) return 1;
            Int<MOD> a = pow(t >> 1);
            a *= a;
            if (t&1) a *= *this;
            return a;
        }

        Int inv() const { return pow(MOD - 2);}
        Int& operator/=(const Int<MOD> a) { return *this *= a.inv();}
        Int operator/(const Int<MOD> a) const { return Int<MOD>(*this) /= a;}
    };
}
std::istream& operator>>(std::istream& is, const mod::Int<MOD>& a) { return is >> a.x;}
std::ostream& operator<<(std::ostream& os, const mod::Int<MOD>& a) { return os << a.x;}

class EApolloVersusPan {
public:
    void solve(std::istream& in, std::ostream& out) {
        int t;
        in >> t;
        vector<mod::Int<MOD>> pows(60);
        rep(pi,0,60) pows[pi] = mod::Int<MOD>(2).pow(pi);
        rep(ti,0,t) {
            int n;
            in >> n;
            vector<ll> x(n);
            rep(i,0,n) in >> x[i];
            mod::Int<MOD> answer;
            vector<int> cnt(60);
            rep(i,0,n) rep(j,0,60) {
                if (1LL << j & x[i]) ++cnt[j];
            }
            rep(i,0,n) {
                mod::Int<MOD> orsum, andsum;
                rep(j,0,60) {
                    if (1LL << j & x[i]) {
                        orsum += pows[j] * n;
                        andsum += pows[j] * cnt[j];
                    } else {
                        orsum += pows[j] * cnt[j];
                    }
                }
                answer += orsum * andsum;
            }
            out << answer << endl;
        }
    }
};


signed main() {
    EApolloVersusPan solver;
    std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

```