//dragon->emperor
#include <bits/stdc++.h>

using namespace std;

/**********************************************************************************/

#define mod 1000000007
#define mod2 998244353
const double pi = acos(-1);
#define inf 1e18+5
#define iinf 1e9+5

#define ll long long
#define ld  long double
#define fl(i,a,n) for(ll i=a;i<n;i++)
#define lf(i,a,n) for(ll i=n-1;i>=a;i--)
#define read(n) ll n; cin>>n;
#define scan(a,n) vector<ll> a(n); for(ll i=0;i<n;i++) cin>>a[i];
#define print(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout<<endll;
#define p(n) cout<<n<<endll;

#define endll "\n"
#define pb push_back
#define mp make_pair
#define dec(n) fixed<<setprecision(n)
#define F first
#define S second
#define I insert
#define E end()
#define B begin()

#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
#define reverseall(x) reverse(all(x))

typedef vector<ll> vl;
typedef pair<ll,ll> pll;
typedef map<ll,ll> mll;
typedef vector<pll> vpl;
/*************************************[DEBUG]**************************************/
 
void debug(ll x) { cout<<x<<endll;}
void debug(int x) { cout<<x<<endll;}
void debug(unsigned int x) { cout<<x<<endll;}
void debug(unsigned ll x) { cout<<x<<endll;}
void debug(float x) { cout<<x<<endll;}
void debug(double x) { cout<<dec(7)<<x<<endll;}
void debug(ld x) { cout<<dec(15)<<x<<endll;}
void debug(char x) { cout<<'\''<<x<<'\''<<endll;}
void debug(string s) {cout<<'\"'<<s<<'\"'<<endll;}
void debug(vector<ll> v) { for(auto x :v) cout<<x<<" "; cout<<endll;}
void debug(bool bb)  { cout<<(bb? "True":"False")<<endll;} 
void debug(map<ll,ll>mpp) { for(auto x :mpp) cout<<x.first<<" "<<x.second<<endll;}
void debug(pair<ll, ll> pp) { cout<<"{"<<pp.first<<","<<pp.second<<"}"<<endll;} 
void debug(vector<pair<ll,ll>> v) { for(auto x :v) debug(x);}

/***********************************[FUNCTIONS]************************************/

void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

// bitset<200000>vis(0);
vector<bool> prime;

void primes(ll n)
{
    prime.resize(n+1);
    prime.assign(n+1,true);
    prime[0]=0;
    prime[1]=0;
    for(ll i=2; i*i<=n; i++)
    {
        if(prime[i])
        {
            for(ll j=(i*i); j<n; j=j+i) prime[j]=false;
        }
    }
}

ll gcd(ll x, ll y)
{
    if(x==0) return y;
    return gcd((ll) y%x, (ll)x);
}

ll powM(ll x, ll y, ll m)
{
    ll ans=1, r=1;
    x=x%m;
    while(r>0 && r<=y)
    {
        if(r & y)
        {
            ans=ans*x;
            ans=ans%m;
        }
        r=r<<1;
        x=x*x;
        x=x%m;
    }
    return ans;
}

ll powN(ll a,ll n)
{
    if(n==0) return 1;
    if(n==1) return a;
    ll u=powN(a,n/2);
    u=u*u;
    if(n%2) u=u*a;
    return u;
}

ll modinv(ll a,ll m)
{
    return powM(a,m-2,m);
}

ll ncr(ll n, ll r, ll m)
{
    if(n<r) return 0;
    if(n==r || r==0) return 1;
    if(r==1) return n;
    if(n-r<r) return ncr(n,n-r,m);
    ll a=n;
    ll b=r;
    for(ll i=1; i<r; i++)
    {
        a=(a*(n-i))%m;
        b=(b*(r-i))%m;
    }
    b=modinv(b,m);
    a=(a*b)%m;
    return a;
}

/************************************[CODE]****************************************/

void solve()
{
    ll n; cin>>n;
    vl a(n),bits(61,0);
    fl(i,0,n) cin>>a[i];
    fl(i,0,n)
    {
        fl(j,0,61)
        {
            if(a[i] & (1ll << j)) bits[j]++;
        }
    }
    ll ans=0;
    fl(i,0,n)
    {
        ll sum_and=0;
        ll sum_or=0;
        fl(j,0,61)
        {
            ll k=((1ll << j)+mod)%mod;
            if((a[i] & (1ll << j)))
            {
                sum_and+=(bits[j]*k);
                sum_or+=(n*k);
            }
            else 
            {
                sum_or+=(bits[j]*k);
            }
            sum_or=(sum_or+mod)%mod;
            sum_and=(sum_and+mod)%mod;
        }
        ans+=(sum_or * sum_and);
        ans=(ans+mod)%mod;
    }
    p(ans);
}

int main()
{
    fast();
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}


### 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
//dragon->emperor
#include <bits/stdc++.h>

using namespace std;

/**********************************************************************************/

#define mod 1000000007
#define mod2 998244353
const double pi = acos(-1);
#define inf 1e18+5
#define iinf 1e9+5

#define ll long long
#define ld  long double
#define fl(i,a,n) for(ll i=a;i<n;i++)
#define lf(i,a,n) for(ll i=n-1;i>=a;i--)
#define read(n) ll n; cin>>n;
#define scan(a,n) vector<ll> a(n); for(ll i=0;i<n;i++) cin>>a[i];
#define print(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout<<endll;
#define p(n) cout<<n<<endll;

#define endll "\n"
#define pb push_back
#define mp make_pair
#define dec(n) fixed<<setprecision(n)
#define F first
#define S second
#define I insert
#define E end()
#define B begin()

#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
#define reverseall(x) reverse(all(x))

typedef vector<ll> vl;
typedef pair<ll,ll> pll;
typedef map<ll,ll> mll;
typedef vector<pll> vpl;
/*************************************[DEBUG]**************************************/
 
void debug(ll x) { cout<<x<<endll;}
void debug(int x) { cout<<x<<endll;}
void debug(unsigned int x) { cout<<x<<endll;}
void debug(unsigned ll x) { cout<<x<<endll;}
void debug(float x) { cout<<x<<endll;}
void debug(double x) { cout<<dec(7)<<x<<endll;}
void debug(ld x) { cout<<dec(15)<<x<<endll;}
void debug(char x) { cout<<'\''<<x<<'\''<<endll;}
void debug(string s) {cout<<'\"'<<s<<'\"'<<endll;}
void debug(vector<ll> v) { for(auto x :v) cout<<x<<" "; cout<<endll;}
void debug(bool bb)  { cout<<(bb? "True":"False")<<endll;} 
void debug(map<ll,ll>mpp) { for(auto x :mpp) cout<<x.first<<" "<<x.second<<endll;}
void debug(pair<ll, ll> pp) { cout<<"{"<<pp.first<<","<<pp.second<<"}"<<endll;} 
void debug(vector<pair<ll,ll>> v) { for(auto x :v) debug(x);}

/***********************************[FUNCTIONS]************************************/

void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

// bitset<200000>vis(0);
vector<bool> prime;

void primes(ll n)
{
    prime.resize(n+1);
    prime.assign(n+1,true);
    prime[0]=0;
    prime[1]=0;
    for(ll i=2; i*i<=n; i++)
    {
        if(prime[i])
        {
            for(ll j=(i*i); j<n; j=j+i) prime[j]=false;
        }
    }
}

ll gcd(ll x, ll y)
{
    if(x==0) return y;
    return gcd((ll) y%x, (ll)x);
}

ll powM(ll x, ll y, ll m)
{
    ll ans=1, r=1;
    x=x%m;
    while(r>0 && r<=y)
    {
        if(r & y)
        {
            ans=ans*x;
            ans=ans%m;
        }
        r=r<<1;
        x=x*x;
        x=x%m;
    }
    return ans;
}

ll powN(ll a,ll n)
{
    if(n==0) return 1;
    if(n==1) return a;
    ll u=powN(a,n/2);
    u=u*u;
    if(n%2) u=u*a;
    return u;
}

ll modinv(ll a,ll m)
{
    return powM(a,m-2,m);
}

ll ncr(ll n, ll r, ll m)
{
    if(n<r) return 0;
    if(n==r || r==0) return 1;
    if(r==1) return n;
    if(n-r<r) return ncr(n,n-r,m);
    ll a=n;
    ll b=r;
    for(ll i=1; i<r; i++)
    {
        a=(a*(n-i))%m;
        b=(b*(r-i))%m;
    }
    b=modinv(b,m);
    a=(a*b)%m;
    return a;
}

/************************************[CODE]****************************************/

void solve()
{
    ll n; cin>>n;
    vl a(n),bits(61,0);
    fl(i,0,n) cin>>a[i];
    fl(i,0,n)
    {
        fl(j,0,61)
        {
            if(a[i] & (1ll << j)) bits[j]++;
        }
    }
    ll ans=0;
    fl(i,0,n)
    {
        ll sum_and=0;
        ll sum_or=0;
        fl(j,0,61)
        {
            ll k=((1ll << j)+mod)%mod;
            if((a[i] & (1ll << j)))
            {
                sum_and+=(bits[j]*k);
                sum_or+=(n*k);
            }
            else 
            {
                sum_or+=(bits[j]*k);
            }
            sum_or=(sum_or+mod)%mod;
            sum_and=(sum_and+mod)%mod;
        }
        ans+=(sum_or * sum_and);
        ans=(ans+mod)%mod;
    }
    p(ans);
}

int main()
{
    fast();
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}


```