#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define min3(a, b, c) min(c, min(a, b))
#define min4(a, b, c, d) min(d, min(c, min(a, b)))
#define max3(a, b, c) max(c, max(a, b))
#define max4(a, b, c, d) max(d, max(c, max(a, b)))
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

ll nCrevenoroddfinder(ll n,ll r)
{
    ll a=r;
    ll b=n-r;
    for(ll i=0;i<30;i++)
    {
        ll x=1<<i;
        if((x&a)&&(x&b))
        {
            return 0;//even
        }
    }
    return 1;//odd
}

// for calculating inverse
int modx(int x,int n)
{
    int result=1,M=1e9+7;
    while(n>0)
    {
        if(n % 2 ==1)
            result=(result * x)%M;
        x=(x*x)%M;
        n=n/2;
    }
    return result;
}

ll ncr(ll n, ll k) 
{ 
    ll res = 1;  
    if (k > n - k) 
        k = n - k; 
    for (ll i = 0; i < k; ++i) { 
        res*=(n-i);
		res /= (i + 1); 
    } 
  
    return res; 
} 

ll add(ll a,ll b,ll m){
	return ((a%m)+(b%m))%m;
}

ll sub(ll a,ll b,ll m){
	return ((a%m)-(b%m)+m)%m;
}

ll mul(ll a,ll b,ll m){
	return ((a%m)*(b%m))%m;
}

ll inverse(ll a,ll m){
	return modx(a,m-2);
}

ll power(ll x,ll n){
	ll res=1;
	while(n>0){
		if(n%2==1)
		res=(res*x);
		x=x*x;
		n/=2;
	}
	return res;
}


ll gcd(ll a,ll b){
	if(b==0)
	return a;
	else
	return gcd(b,a%b);
}

ll lcm(ll a,ll b){
	return (a*b)/(gcd(a,b));
}


bool isprime(ll n) {
  for (ll i = 2; i * i <= n; i++) {
    if (n % i == 0)return false;
  }
  return true;
}

bool isperfect(ll n) {
  ll y = sqrt(n);
  if (n % y == 0 && y * y == n)return true;
  return false;
}

bool prime[10000000];
void seive() {
    for(ll i=1;i<10000000;i++)
    prime[i]=true;
	prime[1] = true;
	for (ll i = 2; i * i < 10000000; i++) {
		if (!prime[i])continue;
		for (ll j = i * i; j < 10000000; j += i) {
		  prime[j] = false;
		}
	
	}
}

int32_t main(){
	fast
	ll t,n,i,j;
	cin>>t;
	while(t--){
		cin>>n;ll a[n];
		for(i=0;i<n;i++)cin>>a[i];
		ll ad=a[0],cnt=0,mod=1e9+7;
		for(i=1;i<n;i++)ad=ad&a[i];
		for(i=0;i<n;i++){
			if(a[i]==ad)cnt++;
		}
		ll ans=mul(cnt,cnt-1,mod);
		for(i=1;i<=n-2;i++)
		ans=mul(ans,i,mod);
		if(cnt==0)ans=0;
		cout<<ans<<"\n";
	}
	return 0;
}


### Prompt

Please provide a Cpp coded solution to the problem described below:

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
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define min3(a, b, c) min(c, min(a, b))
#define min4(a, b, c, d) min(d, min(c, min(a, b)))
#define max3(a, b, c) max(c, max(a, b))
#define max4(a, b, c, d) max(d, max(c, max(a, b)))
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

ll nCrevenoroddfinder(ll n,ll r)
{
    ll a=r;
    ll b=n-r;
    for(ll i=0;i<30;i++)
    {
        ll x=1<<i;
        if((x&a)&&(x&b))
        {
            return 0;//even
        }
    }
    return 1;//odd
}

// for calculating inverse
int modx(int x,int n)
{
    int result=1,M=1e9+7;
    while(n>0)
    {
        if(n % 2 ==1)
            result=(result * x)%M;
        x=(x*x)%M;
        n=n/2;
    }
    return result;
}

ll ncr(ll n, ll k) 
{ 
    ll res = 1;  
    if (k > n - k) 
        k = n - k; 
    for (ll i = 0; i < k; ++i) { 
        res*=(n-i);
		res /= (i + 1); 
    } 
  
    return res; 
} 

ll add(ll a,ll b,ll m){
	return ((a%m)+(b%m))%m;
}

ll sub(ll a,ll b,ll m){
	return ((a%m)-(b%m)+m)%m;
}

ll mul(ll a,ll b,ll m){
	return ((a%m)*(b%m))%m;
}

ll inverse(ll a,ll m){
	return modx(a,m-2);
}

ll power(ll x,ll n){
	ll res=1;
	while(n>0){
		if(n%2==1)
		res=(res*x);
		x=x*x;
		n/=2;
	}
	return res;
}


ll gcd(ll a,ll b){
	if(b==0)
	return a;
	else
	return gcd(b,a%b);
}

ll lcm(ll a,ll b){
	return (a*b)/(gcd(a,b));
}


bool isprime(ll n) {
  for (ll i = 2; i * i <= n; i++) {
    if (n % i == 0)return false;
  }
  return true;
}

bool isperfect(ll n) {
  ll y = sqrt(n);
  if (n % y == 0 && y * y == n)return true;
  return false;
}

bool prime[10000000];
void seive() {
    for(ll i=1;i<10000000;i++)
    prime[i]=true;
	prime[1] = true;
	for (ll i = 2; i * i < 10000000; i++) {
		if (!prime[i])continue;
		for (ll j = i * i; j < 10000000; j += i) {
		  prime[j] = false;
		}
	
	}
}

int32_t main(){
	fast
	ll t,n,i,j;
	cin>>t;
	while(t--){
		cin>>n;ll a[n];
		for(i=0;i<n;i++)cin>>a[i];
		ll ad=a[0],cnt=0,mod=1e9+7;
		for(i=1;i<n;i++)ad=ad&a[i];
		for(i=0;i<n;i++){
			if(a[i]==ad)cnt++;
		}
		ll ans=mul(cnt,cnt-1,mod);
		for(i=1;i<=n-2;i++)
		ans=mul(ans,i,mod);
		if(cnt==0)ans=0;
		cout<<ans<<"\n";
	}
	return 0;
}


```