#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include <iostream>
#include <algorithm>
#include <map>
#include <math.h>
#include <climits>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <numeric>
#include <iostream>
#include <vector>
#include <numeric>
#include <string>
#include <functional>
#include <stdio.h>
#include <string.h>
#include <iomanip>
#include <numeric>//
#define ll long long
#define REP(i, n) for (ll i = 0; i < n; i++)
#define PER(i, n) for (ll i = n - 1; i >= 0; i--)
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define per(i, b, a) for (ll i = b; i >= a; i--)
#define mod 1000000007
#define ull unsigned long long
#define mem1(a)  memset(a,-1,sizeof(a))
#define mem0(a)  memset(a,0,sizeof(a))
#define sc second
#define fi first
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define endl "\n"
const long long INF=1e18;
using namespace std;
 
ll hcf(ll a, ll b)
{
    if (b == 0)
        return a;
    return hcf(b, a % b);
}
ull stringtoll(string s)
{
    ull ans = 0;
    for (ull i = 0; i < s.length(); i++)
    {
        ans = ans *10 + (s[i] - '0');
    }
    return ans;
}
 
vector<ll> root(ll n)
{
    vector<ll> ans;
    for (ll i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            ans.push_back(i);
            if (i != n / i)
                ans.push_back(n / i);
        }
    }
    return ans;
}
 
bool ifprime(ll n)
{
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}
 
ll logat(ll n, ll base)
{
    return (log(n) / log(base));
}
 
ll factorial(ll n)
{
    if (n == 0)
        return 1;
    return (n* factorial(n - 1)) % mod;
}
 
void baspri(bool flag)
{
    if(flag)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
}
 
ll lcm(ll a, ll b)
{
    return (a / hcf(a, b)) * b;
}
 
vector<pair<ll,ll>> prime_fact(ll n)
{
    vector<pair<ll,ll>>ans;
    for(ll i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            ll another=0;
            while(n%i==0)
            {
                n=n/i;
                another++;
            }
            ans.push_back({i,another});
        }
    }
    if(n>1)
        ans.push_back({n,1});
    return ans;
}
 
 
ll pw(ll n,ll r,ll mop)
{
    ll res=1;
    while(r!=0)
    {
        if(r%2)
        {
            res=(res*n)%mop;
            r--;
        }
        n=(n*n)%mop;
        r=r/2;
    }
    return res;
}
 
//#define SIEVE
//const int N=1000005;
//vector<bool>prime(N,true);
//void sieve()
//{
//    prime[0]=false;
//    prime[1]=false;
//    for (int p = 2; p * p < N; p++)
//    {
//        if (prime[p] == true)
//        {
//            for (int i = p * p; i < N; i += p)
//                prime[i] = false;
//        }
//    }
//}
 
int query()
{
    int t;
    cin>>t;
    return t;
}

int main()
{
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    #ifdef SIEVE
        sieve();
    #endif
    
    ll t;
    cin>>t;

    while(t--)
    {
        ll n;
        cin>>n;
        
        vector<ll>v(n);
        
        REP(i,n)
            cin>>v[i];
        ll no=v[0]&v[1];
        
        rep(i,2,n)
            no=v[i]&no;
        
        ll cnt=0;
        
        REP(i,n)
        {
            if(v[i]==no)
            cnt++;
        }
        ll ans=((cnt*(cnt-1)));
        ans=((ans%mod)*(factorial(n-2)))%mod;
        cout<<ans<<endl;
    }
}


### Prompt

Construct a CPP code solution to the problem outlined:

A sequence of n non-negative integers (n ≥ 2) a_1, a_2, ..., a_n is called good if for all i from 1 to n-1 the following condition holds true: $$$a_1 \: \& \: a_2 \: \& \: ... \: \& \: a_i = a_{i+1} \: \& \: a_{i+2} \: \& \: ... \: \& \: a_n, where \&$$$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND).

You are given an array a of size n (n ≥ 2). Find the number of permutations p of numbers ranging from 1 to n, for which the sequence a_{p_1}, a_{p_2}, ... ,a_{p_n} is good. Since this number can be large, output it modulo 10^9+7.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^4), denoting the number of test cases.

The first line of each test case contains a single integer n (2 ≤ n ≤ 2 ⋅ 10^5) — the size of the array.

The second line of each test case contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 10^9) — the elements of the array.

It is guaranteed that the sum of n over all test cases doesn't exceed 2 ⋅ 10^5.

Output

Output t lines, where the i-th line contains the number of good permutations in the i-th test case modulo 10^9 + 7.

Example

Input


4
3
1 1 1
5
1 2 3 4 5
5
0 2 0 3 0
4
1 3 5 1


Output


6
0
36
4

Note

In the first test case, since all the numbers are equal, whatever permutation we take, the sequence is good. There are a total of 6 permutations possible with numbers from 1 to 3: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].

In the second test case, it can be proved that no permutation exists for which the sequence is good.

In the third test case, there are a total of 36 permutations for which the sequence is good. One of them is the permutation [1,5,4,2,3] which results in the sequence s=[0,0,3,2,0]. This is a good sequence because 

  *  s_1 = s_2 \: \& \: s_3 \: \& \: s_4 \: \& \: s_5 = 0, 
  *  s_1 \: \& \: s_2 = s_3 \: \& \: s_4 \: \& \: s_5 = 0, 
  *  s_1 \: \& \: s_2 \: \& \: s_3 = s_4 \: \& \: s_5 = 0, 
  *  s_1 \: \& \: s_2 \: \& \: s_3 \: \& \: s_4 = s_5 = 0. 

### Response

```cpp
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include <iostream>
#include <algorithm>
#include <map>
#include <math.h>
#include <climits>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <numeric>
#include <iostream>
#include <vector>
#include <numeric>
#include <string>
#include <functional>
#include <stdio.h>
#include <string.h>
#include <iomanip>
#include <numeric>//
#define ll long long
#define REP(i, n) for (ll i = 0; i < n; i++)
#define PER(i, n) for (ll i = n - 1; i >= 0; i--)
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define per(i, b, a) for (ll i = b; i >= a; i--)
#define mod 1000000007
#define ull unsigned long long
#define mem1(a)  memset(a,-1,sizeof(a))
#define mem0(a)  memset(a,0,sizeof(a))
#define sc second
#define fi first
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define endl "\n"
const long long INF=1e18;
using namespace std;
 
ll hcf(ll a, ll b)
{
    if (b == 0)
        return a;
    return hcf(b, a % b);
}
ull stringtoll(string s)
{
    ull ans = 0;
    for (ull i = 0; i < s.length(); i++)
    {
        ans = ans *10 + (s[i] - '0');
    }
    return ans;
}
 
vector<ll> root(ll n)
{
    vector<ll> ans;
    for (ll i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            ans.push_back(i);
            if (i != n / i)
                ans.push_back(n / i);
        }
    }
    return ans;
}
 
bool ifprime(ll n)
{
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}
 
ll logat(ll n, ll base)
{
    return (log(n) / log(base));
}
 
ll factorial(ll n)
{
    if (n == 0)
        return 1;
    return (n* factorial(n - 1)) % mod;
}
 
void baspri(bool flag)
{
    if(flag)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
}
 
ll lcm(ll a, ll b)
{
    return (a / hcf(a, b)) * b;
}
 
vector<pair<ll,ll>> prime_fact(ll n)
{
    vector<pair<ll,ll>>ans;
    for(ll i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            ll another=0;
            while(n%i==0)
            {
                n=n/i;
                another++;
            }
            ans.push_back({i,another});
        }
    }
    if(n>1)
        ans.push_back({n,1});
    return ans;
}
 
 
ll pw(ll n,ll r,ll mop)
{
    ll res=1;
    while(r!=0)
    {
        if(r%2)
        {
            res=(res*n)%mop;
            r--;
        }
        n=(n*n)%mop;
        r=r/2;
    }
    return res;
}
 
//#define SIEVE
//const int N=1000005;
//vector<bool>prime(N,true);
//void sieve()
//{
//    prime[0]=false;
//    prime[1]=false;
//    for (int p = 2; p * p < N; p++)
//    {
//        if (prime[p] == true)
//        {
//            for (int i = p * p; i < N; i += p)
//                prime[i] = false;
//        }
//    }
//}
 
int query()
{
    int t;
    cin>>t;
    return t;
}

int main()
{
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    #ifdef SIEVE
        sieve();
    #endif
    
    ll t;
    cin>>t;

    while(t--)
    {
        ll n;
        cin>>n;
        
        vector<ll>v(n);
        
        REP(i,n)
            cin>>v[i];
        ll no=v[0]&v[1];
        
        rep(i,2,n)
            no=v[i]&no;
        
        ll cnt=0;
        
        REP(i,n)
        {
            if(v[i]==no)
            cnt++;
        }
        ll ans=((cnt*(cnt-1)));
        ans=((ans%mod)*(factorial(n-2)))%mod;
        cout<<ans<<endl;
    }
}


```