#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vii;
typedef pair<ll, ll> pii;
typedef vector< pii > vpi;
typedef vector< vii > vvi;

#define present(container, element) (container.find(element) != container.end())
#define tr(container, it) for(decltype(container.begin()) it = container.begin(); it != container.end(); it++)
#define F(i, m, n) for(int(i) = m; i < n; ++i)
#define FR(i, k, n) for(int(i) = n-1; i >= k; --i)
#define f(i, n)  F(i, 0, n)
#define fr(i, n) FR(i, 0, n)
#define p1(x) cout << x <<"\n";
#define p2(x,y) cout << x << " " << y << "\n";
#define p3(x,y,z) cout << x << " " << y << " " << z << "\n";
#define px(a) for(auto x: a) cout<<x<<" "; cout<<'\n';
#define o1(x) cin >> x;
#define o2(x,y) cin >> x >> y;
#define o3(x,y,z) cin >> x >> y >> z;
#define pi 3.1415926535897932384626
#define mod 1000000007
#define all(a)  (a).begin(), (a).end()
#define rall(a)  (a).rbegin(), (a).rend()
#define pb push_back
#define endl '\n'
#define mem(a,x) memset(a,x,sizeof(a))              //set elements of array to some value
#define siz 256
#define bc(n) __builtin_popcountll(n)
#define leadzero(a) __builtin_clz(a)        // count leading zeroes
#define trailzero(a) __builtin_ctz(a)       // count trailing zeroes
#define bitcount(a) __builtin_popcount(a)   // count set bits
#define lps(v,x) (lower_bound(all(v),x)-v.begin())
#define ups(v,x) (upper_bound(all(v),x)-v.begin())
#define ff first
#define ss second
#define mp(a,b) make_pair(a, b)
#define ppb pop_back
#define sz(a) a.size()
#define ins insert
#define llmax 5000000000000000005

ll ESP=1e18;
//#########################################################################################
bool isPrime[1000000];
void sieve(long long int N)
{
    for(ll i = 0; i <= N; ++i)
    {
        isPrime[i] = true;
    }
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i = 2; i * i <= N; ++i)
    {
        if(isPrime[i] == true)
        {
            for(int j = i * i; j <= N ; j += i)
                isPrime[j] = false;
        }
    }
}

//#########################################################################################
bool anagram(char *s1, char *s2)
{
    ll count[siz];
    mem(count,0) ;
    ll i;
    for (i = 0; s1[i] && s2[i];  i++)
    {
        count[s1[i]]++;
        count[s2[i]]--;
    }
    if (s1[i] || s2[i])
    {
        return false;
    }
    F(i,0,siz)
    {
        if (count[i])
        {
            return false;
        }
    }
    return true;

}
//###########################################################################################
int find_largest_digit(int n)
{
    int mx = 0 ;
    while(n>0)
    {
        mx = max(mx, n%10) ;
        n/=10 ;
    }
    return mx  ;
}
//###########################################################################################
ll no_of_digits(ll n)
{
    ll ans = 0 ;
    while(n>0)
    {
        ans++;
        n/=10 ;
    }
    return ans ;
}
//###########################################################################################
// modulo Multiplication
ll moduloMultiplication(ll  a, ll  b,  ll  zz)
{
    ll res = 0;
    a %= zz;
    while (b)
    {
        if (b & 1)
            res = (res + a) % zz;

        a = (2 * a) % zz;

        b >>= 1;
    }
    return res;
}
//###########################################################################################
ll to_int(string s)
{
    bool o = true ;
    ll ans = 0 ;
    for(ll i=0; i<s.length(); i++)
    {
        ans = ans*10 + (s[i]-48) ;
    }
    return ans ;
}
//###########################################################################################
//function to calculate a^b under mod...
inline ll powmod(ll x, ll n, ll m)
{
    if(n==0 || x==1)
        return 1;
    else if(n%2==0)
    {
        return powmod((x*x)%m,n/2,m);
    }
    else
    {
        return x*(powmod((x*x)%m,(n-1)/2,m))%m;
    }
}
//###########################################################################################
ll poww(ll a,ll b)
{
    if(b==0 || a==1) return 1;
    ll half=poww(a,(b/2));
    if(half<0 || half>ESP) return -1;
    ll full = (half*half);
    if (half != 0 && full / half != half)
    {
        return -1;
    }

    if(b%2)
    {
        if(full*a<0 || full*a>ESP) return -1;
    }
    if(full<0 || full>ESP) return -1;

    if(b%2)
    {
        ll x = a*full;
        if (a != 0 && x / a != full)
        {
            return -1;
        }
        return (x);
    }
    return full;
}
//###########################################################################################
//function to calculate inverse modulo under mod...assuming gcd is 1
ll invmod(ll a,ll modulo)
{
    ll check=powmod(a,modulo-2,modulo) %modulo;
    return check;
}
//###########################################################################################

ll max(ll a,ll b)
{
    if (a>b)
    {
        return a;
    }
    return b;
}
//###########################################################################################
ll min(ll a,ll b)
{
    if (a<b)
    {
        return a;
    }
    return b;
}
//###########################################################################################
ll min(ll a,int b)
{
    if (a<b) return a;
    return b;
}
//###########################################################################################
ll min(int a,ll b)
{
    if (a<b) return a;
    return b;
}
//###########################################################################################
ll max(ll a,int b)
{
    if (a>b) return a;
    return b;
}
//###########################################################################################
ll max(int a,ll b)
{
    if (a>b) return a;
    return b;
}
//###########################################################################################
ll gcd(ll a,ll b)
{
    if (b==0) return a;
    return gcd(b,a%b);
}
//###########################################################################################
ll lcm(ll a,ll b)
{
    return a/gcd(a,b)*b;
}
//###########################################################################################
void yes()
{
    cout<<"YES"<<"\n";
}
//###########################################################################################
void no()
{
    cout<<"NO"<<"\n";
}
//###########################################################################################
vector<int> factorize(int n)
{
    vector<int> res;
    for (int i = 2; i * i <= n; ++i)
    {
        while (n % i == 0)
        {
            res.push_back(i);
            n /= i;
        }
    }
    if (n != 1)
    {
        res.push_back(n);
    }
    return res;
}
//###########################################################################################
void printDivisors(int n)
{
    for (int i=1; i<=sqrt(n); i++)
    {
        if (n%i == 0)
        {
            if (n/i == i)
                printf("%d ", i);

            else
                printf("%d %d ", i, n/i);
        }
    }
}
//###########################################################################################
int phi(int n)
{
    int result = n;
    for (int p = 2; p * p <= n; ++p)
    {

        if (n % p == 0)
        {

            while (n % p == 0)
                n /= p;
            result -= result / p;
        }
    }

    if (n > 1)
        result -= result / n;
    return result;
}
//###########################################################################################
bool presents(vii v, int x)
{
    bool flag = false;
    tr(v,it)
    {
        if(*it==x)
            flag = true;
    }
    return flag;
}
//###########################################################################################
ll ncr(ll n, ll r)
{
    if(n<r)
        return 0;
    long long p = 1, k = 1;
    if (n - r < r)
        r = n - r;

    if (r != 0)
    {
        while (r)
        {
            p *= n;
            k *= r;
            long long m = gcd(p, k);
            p /= m;
            k /= m;

            n--;
            r--;
        }
    }
    else
        p = 1;
    return p;
}
//###########################################################################################
int tc(char c)
{
    int k = c -97;
    return k;
}
//###########################################################################################
ll modFact(ll n)
{
    ll p = mod;
    if (n >= p)
        return 0;

    ll result = 1;
    for (ll i = 1; i <= n; i++)
        result = (result * i) % p;

    return result;
}
unsigned long long power(unsigned long long x,
                                  int y, int p)
{
    unsigned long long res = 1; // Initialize result

    x = x % p; // Update x if it is more than or
    // equal to p

    while (y > 0)
    {

        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;

        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}

// Returns n^(-1) mod p
unsigned long long modInverse(unsigned long long n,
                                            int p)
{
    return power(n, p - 2, p);
}

// Returns nCr % p using Fermat's little
// theorem.
unsigned long long nCrModPFermat(unsigned long long n,
                                 ll r)
{
    ll p =mod;
    // If n<r, then nCr should return 0
    if (n < r)
        return 0;
    // Base case
    if (r == 0)
        return 1;

    // Fill factorial array so that we
    // can find all factorial of r, n
    // and n-r
    unsigned long long fac[n + 1];
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = (fac[i - 1] * i) % p;

    return (fac[n] * modInverse(fac[r], p) % p
            * modInverse(fac[n - r], p) % p)
           % p;
}

void okms()
{
    ll n;
    cin >> n;
    ll arr[n];
    f(i,n) cin >> arr[i];
    map<ll,ll> xrr;
    f(i,n) xrr[arr[i]]++;
    ll an = arr[0]&arr[1];
    F(i,2,n) an &= arr[i];
    if(xrr[an]>1)
    {
        ll k;
        k = nCrModPFermat(xrr[an],2);
        k = (k*2)%mod;
        k = (k*modFact(n-2))%mod;
        cout << k << endl;
        return;
    }
    p1(0)
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << showpoint;
    cout.precision(15);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ll test;
    //test = 1;
    cin >> test;
    f(i,test)
    {
        okms();
    }
    return 0;
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

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 optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vii;
typedef pair<ll, ll> pii;
typedef vector< pii > vpi;
typedef vector< vii > vvi;

#define present(container, element) (container.find(element) != container.end())
#define tr(container, it) for(decltype(container.begin()) it = container.begin(); it != container.end(); it++)
#define F(i, m, n) for(int(i) = m; i < n; ++i)
#define FR(i, k, n) for(int(i) = n-1; i >= k; --i)
#define f(i, n)  F(i, 0, n)
#define fr(i, n) FR(i, 0, n)
#define p1(x) cout << x <<"\n";
#define p2(x,y) cout << x << " " << y << "\n";
#define p3(x,y,z) cout << x << " " << y << " " << z << "\n";
#define px(a) for(auto x: a) cout<<x<<" "; cout<<'\n';
#define o1(x) cin >> x;
#define o2(x,y) cin >> x >> y;
#define o3(x,y,z) cin >> x >> y >> z;
#define pi 3.1415926535897932384626
#define mod 1000000007
#define all(a)  (a).begin(), (a).end()
#define rall(a)  (a).rbegin(), (a).rend()
#define pb push_back
#define endl '\n'
#define mem(a,x) memset(a,x,sizeof(a))              //set elements of array to some value
#define siz 256
#define bc(n) __builtin_popcountll(n)
#define leadzero(a) __builtin_clz(a)        // count leading zeroes
#define trailzero(a) __builtin_ctz(a)       // count trailing zeroes
#define bitcount(a) __builtin_popcount(a)   // count set bits
#define lps(v,x) (lower_bound(all(v),x)-v.begin())
#define ups(v,x) (upper_bound(all(v),x)-v.begin())
#define ff first
#define ss second
#define mp(a,b) make_pair(a, b)
#define ppb pop_back
#define sz(a) a.size()
#define ins insert
#define llmax 5000000000000000005

ll ESP=1e18;
//#########################################################################################
bool isPrime[1000000];
void sieve(long long int N)
{
    for(ll i = 0; i <= N; ++i)
    {
        isPrime[i] = true;
    }
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i = 2; i * i <= N; ++i)
    {
        if(isPrime[i] == true)
        {
            for(int j = i * i; j <= N ; j += i)
                isPrime[j] = false;
        }
    }
}

//#########################################################################################
bool anagram(char *s1, char *s2)
{
    ll count[siz];
    mem(count,0) ;
    ll i;
    for (i = 0; s1[i] && s2[i];  i++)
    {
        count[s1[i]]++;
        count[s2[i]]--;
    }
    if (s1[i] || s2[i])
    {
        return false;
    }
    F(i,0,siz)
    {
        if (count[i])
        {
            return false;
        }
    }
    return true;

}
//###########################################################################################
int find_largest_digit(int n)
{
    int mx = 0 ;
    while(n>0)
    {
        mx = max(mx, n%10) ;
        n/=10 ;
    }
    return mx  ;
}
//###########################################################################################
ll no_of_digits(ll n)
{
    ll ans = 0 ;
    while(n>0)
    {
        ans++;
        n/=10 ;
    }
    return ans ;
}
//###########################################################################################
// modulo Multiplication
ll moduloMultiplication(ll  a, ll  b,  ll  zz)
{
    ll res = 0;
    a %= zz;
    while (b)
    {
        if (b & 1)
            res = (res + a) % zz;

        a = (2 * a) % zz;

        b >>= 1;
    }
    return res;
}
//###########################################################################################
ll to_int(string s)
{
    bool o = true ;
    ll ans = 0 ;
    for(ll i=0; i<s.length(); i++)
    {
        ans = ans*10 + (s[i]-48) ;
    }
    return ans ;
}
//###########################################################################################
//function to calculate a^b under mod...
inline ll powmod(ll x, ll n, ll m)
{
    if(n==0 || x==1)
        return 1;
    else if(n%2==0)
    {
        return powmod((x*x)%m,n/2,m);
    }
    else
    {
        return x*(powmod((x*x)%m,(n-1)/2,m))%m;
    }
}
//###########################################################################################
ll poww(ll a,ll b)
{
    if(b==0 || a==1) return 1;
    ll half=poww(a,(b/2));
    if(half<0 || half>ESP) return -1;
    ll full = (half*half);
    if (half != 0 && full / half != half)
    {
        return -1;
    }

    if(b%2)
    {
        if(full*a<0 || full*a>ESP) return -1;
    }
    if(full<0 || full>ESP) return -1;

    if(b%2)
    {
        ll x = a*full;
        if (a != 0 && x / a != full)
        {
            return -1;
        }
        return (x);
    }
    return full;
}
//###########################################################################################
//function to calculate inverse modulo under mod...assuming gcd is 1
ll invmod(ll a,ll modulo)
{
    ll check=powmod(a,modulo-2,modulo) %modulo;
    return check;
}
//###########################################################################################

ll max(ll a,ll b)
{
    if (a>b)
    {
        return a;
    }
    return b;
}
//###########################################################################################
ll min(ll a,ll b)
{
    if (a<b)
    {
        return a;
    }
    return b;
}
//###########################################################################################
ll min(ll a,int b)
{
    if (a<b) return a;
    return b;
}
//###########################################################################################
ll min(int a,ll b)
{
    if (a<b) return a;
    return b;
}
//###########################################################################################
ll max(ll a,int b)
{
    if (a>b) return a;
    return b;
}
//###########################################################################################
ll max(int a,ll b)
{
    if (a>b) return a;
    return b;
}
//###########################################################################################
ll gcd(ll a,ll b)
{
    if (b==0) return a;
    return gcd(b,a%b);
}
//###########################################################################################
ll lcm(ll a,ll b)
{
    return a/gcd(a,b)*b;
}
//###########################################################################################
void yes()
{
    cout<<"YES"<<"\n";
}
//###########################################################################################
void no()
{
    cout<<"NO"<<"\n";
}
//###########################################################################################
vector<int> factorize(int n)
{
    vector<int> res;
    for (int i = 2; i * i <= n; ++i)
    {
        while (n % i == 0)
        {
            res.push_back(i);
            n /= i;
        }
    }
    if (n != 1)
    {
        res.push_back(n);
    }
    return res;
}
//###########################################################################################
void printDivisors(int n)
{
    for (int i=1; i<=sqrt(n); i++)
    {
        if (n%i == 0)
        {
            if (n/i == i)
                printf("%d ", i);

            else
                printf("%d %d ", i, n/i);
        }
    }
}
//###########################################################################################
int phi(int n)
{
    int result = n;
    for (int p = 2; p * p <= n; ++p)
    {

        if (n % p == 0)
        {

            while (n % p == 0)
                n /= p;
            result -= result / p;
        }
    }

    if (n > 1)
        result -= result / n;
    return result;
}
//###########################################################################################
bool presents(vii v, int x)
{
    bool flag = false;
    tr(v,it)
    {
        if(*it==x)
            flag = true;
    }
    return flag;
}
//###########################################################################################
ll ncr(ll n, ll r)
{
    if(n<r)
        return 0;
    long long p = 1, k = 1;
    if (n - r < r)
        r = n - r;

    if (r != 0)
    {
        while (r)
        {
            p *= n;
            k *= r;
            long long m = gcd(p, k);
            p /= m;
            k /= m;

            n--;
            r--;
        }
    }
    else
        p = 1;
    return p;
}
//###########################################################################################
int tc(char c)
{
    int k = c -97;
    return k;
}
//###########################################################################################
ll modFact(ll n)
{
    ll p = mod;
    if (n >= p)
        return 0;

    ll result = 1;
    for (ll i = 1; i <= n; i++)
        result = (result * i) % p;

    return result;
}
unsigned long long power(unsigned long long x,
                                  int y, int p)
{
    unsigned long long res = 1; // Initialize result

    x = x % p; // Update x if it is more than or
    // equal to p

    while (y > 0)
    {

        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;

        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}

// Returns n^(-1) mod p
unsigned long long modInverse(unsigned long long n,
                                            int p)
{
    return power(n, p - 2, p);
}

// Returns nCr % p using Fermat's little
// theorem.
unsigned long long nCrModPFermat(unsigned long long n,
                                 ll r)
{
    ll p =mod;
    // If n<r, then nCr should return 0
    if (n < r)
        return 0;
    // Base case
    if (r == 0)
        return 1;

    // Fill factorial array so that we
    // can find all factorial of r, n
    // and n-r
    unsigned long long fac[n + 1];
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = (fac[i - 1] * i) % p;

    return (fac[n] * modInverse(fac[r], p) % p
            * modInverse(fac[n - r], p) % p)
           % p;
}

void okms()
{
    ll n;
    cin >> n;
    ll arr[n];
    f(i,n) cin >> arr[i];
    map<ll,ll> xrr;
    f(i,n) xrr[arr[i]]++;
    ll an = arr[0]&arr[1];
    F(i,2,n) an &= arr[i];
    if(xrr[an]>1)
    {
        ll k;
        k = nCrModPFermat(xrr[an],2);
        k = (k*2)%mod;
        k = (k*modFact(n-2))%mod;
        cout << k << endl;
        return;
    }
    p1(0)
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << showpoint;
    cout.precision(15);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ll test;
    //test = 1;
    cin >> test;
    f(i,test)
    {
        okms();
    }
    return 0;
}

```