//Author -> Samkit Jain
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ll long long int


ll sort(const void *a,const void *b) //qsort(x,n,sizeof(ll),sort)
{
   return(*(ll*)a - *(ll*)b);
}
ll gcd(ll a,ll b)
{
    ll a1,b1;
    if(b!=0)
    {
        a1=b;
        b1=a%b;
        return gcd(a1,b1);
    }
    return a;
}
ll binary(ll n)
{
    ll binary=0,temp=1;
    while(n>0)
    {
        binary=binary+((n%2)*temp);
        n=n/2;
        temp=temp*10;
    }
    return binary;
}
ll no_of_bits(ll n)
{
    return (int)log2(n)+1;
}
ll prime(ll n)
{
    if(n==0 || n==1)
    {
        return 0;
    }
    for(ll i=2;i<=n/2;i++)
    {
        if(n%i==0)
        {return 0;}
    }
    return 1;
}

ll mod = 1e9 + 7;

ll fact(ll n)
{
    if(n==0 || n==1)
    {
        return 1;
    }
    else
    {
        return (n*fact(n-1))%mod;
    }
}

int main()
{
    ll t;
    cin>>t;
    for(ll test=1;test<=t;test++)
    {
        ll n;
        cin>>n;
        map<ll,ll>m;
        ll sure=1;

        for(ll i=1;i<=n;i++)
        {
            ll temp;
            cin>>temp;
            m[temp]++;
        }

        ll ans=0,small;
        auto it = m.begin();
        if(it->second>=2)
        {
            ll p  = it->second;
            ans  += ((p)*(p-1))%mod;
            it->second -= 2;
            small = it->first;
            it++;
            for(  ;it!=m.end(); it++)
            {
                if(((it->first)&small) == small)
                {
                    continue;
                }
                else
                {
                    sure=0;
                    break;
                }
            }
        }
        else
        {
            sure=0;
        }



        if(sure)
        {
            ans *= fact(n-2)%mod;
            cout<<ans%mod<<endl;
        }
        else
        {
            cout<<0<<endl;
        }



    }
    return 0;
}
### Prompt

In CPP, your task is to solve 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
//Author -> Samkit Jain
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ll long long int


ll sort(const void *a,const void *b) //qsort(x,n,sizeof(ll),sort)
{
   return(*(ll*)a - *(ll*)b);
}
ll gcd(ll a,ll b)
{
    ll a1,b1;
    if(b!=0)
    {
        a1=b;
        b1=a%b;
        return gcd(a1,b1);
    }
    return a;
}
ll binary(ll n)
{
    ll binary=0,temp=1;
    while(n>0)
    {
        binary=binary+((n%2)*temp);
        n=n/2;
        temp=temp*10;
    }
    return binary;
}
ll no_of_bits(ll n)
{
    return (int)log2(n)+1;
}
ll prime(ll n)
{
    if(n==0 || n==1)
    {
        return 0;
    }
    for(ll i=2;i<=n/2;i++)
    {
        if(n%i==0)
        {return 0;}
    }
    return 1;
}

ll mod = 1e9 + 7;

ll fact(ll n)
{
    if(n==0 || n==1)
    {
        return 1;
    }
    else
    {
        return (n*fact(n-1))%mod;
    }
}

int main()
{
    ll t;
    cin>>t;
    for(ll test=1;test<=t;test++)
    {
        ll n;
        cin>>n;
        map<ll,ll>m;
        ll sure=1;

        for(ll i=1;i<=n;i++)
        {
            ll temp;
            cin>>temp;
            m[temp]++;
        }

        ll ans=0,small;
        auto it = m.begin();
        if(it->second>=2)
        {
            ll p  = it->second;
            ans  += ((p)*(p-1))%mod;
            it->second -= 2;
            small = it->first;
            it++;
            for(  ;it!=m.end(); it++)
            {
                if(((it->first)&small) == small)
                {
                    continue;
                }
                else
                {
                    sure=0;
                    break;
                }
            }
        }
        else
        {
            sure=0;
        }



        if(sure)
        {
            ans *= fact(n-2)%mod;
            cout<<ans%mod<<endl;
        }
        else
        {
            cout<<0<<endl;
        }



    }
    return 0;
}
```