#include <bits/stdc++.h>
using namespace std;
 
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using VI = vector<int>;
using VL = vector<ll>;
using VVI = vector<vector<int>>;
using VVL = vector<vector<ll>>;
using PII = pair<int,int>;
using PLL = pair<ll, ll>;
 
#define REP(i, _, __) for (int i = (_); i < (__); ++i)
#define PER(i, _, __) for (int i = (_-1); i >= (__); --i)
#define FOR(i, _, __) for (int i = (_); i <= (__); ++i)
#define ROF(i, _, __) for (int i = (_); i >= (__); --i)
#define FC(v, V) for (const auto& v: V)
#define FE(v, V) for (auto& v: V)

#define EB emplace_back
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(),(x).end()
#define LLA(x) (x).rbegin(),(x).rend()
#define pf printf

const double PI = acos(-1.0);

template<typename T>
T MIN(T a, T b) { return min(a, b); }

template<typename First, typename... Rest>
First MIN(First f, Rest... r) { return min(f, MIN(r...)); }

template<typename T>
T MAX(T a, T b) { return max(a, b); }

template<typename First, typename... Rest>
First MAX(First f, Rest... r) { return max(f, MAX(r...)); }

template<typename T>
inline void umin(T& a, const T& b) { if (a > b) a = b; }

template<typename T>
inline void umax(T& a, const T& b) { if (a < b) a = b; }

ll FIRSTTRUE (ll l, ll r, function<bool(ll)> f) {
    ll res = l - 1, mid;
    while(l <= r) {
        mid = (l + r) >> 1;
        if (f(mid)) r = mid - 1, res = mid;
        else l = mid + 1;
    }
    return res;
}

ll LASTTRUE (ll l, ll r, function<bool(ll)> f) {
    ll res = l - 1, mid;
    while(l <= r) {
        mid = (l + r) >> 1;
        if (f(mid)) l = mid + 1, res = mid;
        else r = mid - 1;
    }
    return res;
}

const int __BUFFER_SIZE__ = 1 << 20;
bool NEOF = 1;
int __top;
char __buf[__BUFFER_SIZE__], *__p1 = __buf, *__p2 = __buf, __stk[996];
inline char nc() {
    return __p1 == __p2 && NEOF && (__p2 = (__p1 = __buf) + fread(__buf, 1, __BUFFER_SIZE__, stdin), __p1 == __p2) ? (NEOF = 0, EOF) : *__p1++;
}

#define rd read
template<typename T>
inline bool read(T &x) {
    char c = nc();
    bool f = 0; x = 0;
    while (!isdigit(c)) c == '-' && (f = 1), c = nc();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = nc();
    if (f) x = -x;
    return NEOF;
}

inline bool need(char c) { return (c != '\n') && (c != ' '); }

inline bool read(char& a) {
    while ((a = nc()) && need(a) && NEOF) ;
    return NEOF;
}

inline bool read(char *a) {
    while ((*a = nc()) && need(*a) && NEOF) ++a; 
    *a = '\0';
    return NEOF;
}

inline bool read(double &x) {
    bool f = 0; char c = nc(); x = 0;
    while (!isdigit(c))  { f |= (c == '-'); c = nc(); }
    while (isdigit(c)) { x = x * 10.0 + (c ^ 48); c = nc(); }
    if (c == '.') {
        double temp = 1; c = nc();
        while (isdigit(c)) { temp = temp / 10.0; x = x + temp * (c ^ 48); c = nc(); }
    }
    if (f) x = -x;
    return NEOF;
}

template<typename First, typename... Rest>
inline bool read(First &f, Rest &... r) {
    read(f);
    return read(r...);
}

#define pr print
#define pln println
template<typename T>
inline void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x == 0) { putchar('0'); return; }
    __top = 0;
    while(x) {
        __stk[++__top] = x % 10 + '0';
        x /= 10;
    }
    while(__top) {
        putchar(__stk[__top]);
        --__top;
    }
}

template<typename First, typename... Rest>
inline void print(First f, Rest... r) {
    print(f); putchar(' ');
    print(r...);
}

template<typename T>
inline void println(T x) {
    print(x); 
    putchar('\n');
}

template<typename First, typename... Rest>
inline void println(First f, Rest... r) {
    print(f); putchar(' ');
    println(r...);
}

template<typename T>
void println(const vector<T>& V) {
    for(const auto& v: V) print(v), putchar(' ');
    putchar('\n');
}

#ifdef BACKLIGHT
#include "debug.h"
#else
#define debug(...)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) { return l + rng() % (r - l + 1); }

const int N = 5e5 + 5;
const int M = 3e6 + 5;
const int K = 1e7 + 5;
const int MOD = 1e9 + 7;              // 998244353 1e9 + 7
const int INF = 0x3f3f3f3f;             // 1e9 + 7 0x3f3f3f3f
const ll LLINF = 0x3f3f3f3f3f3f3f3f;    // 1e18 + 9 0x3f3f3f3f3f3f3f3f
const double eps = 1e-8;

ll qp(ll a, ll b, ll p = MOD) { ll r = 1; while(b) { if (b & 1) r = r * a % p; a = a * a % p; b>>= 1; } return r; }
ll inv(ll a) { return qp(a, MOD - 2); }

int add(int x, int y) {
    return x + y >= MOD ? x + y - MOD : x + y;
}
int mul(int x, int y) {
    return 1ll * x * y % MOD;
}
int sub(int x, int y) {
    return x - y < 0 ? x - y + MOD : x - y;
}
int dvd(int x, int y) {
    return 1ll * x * qp(y, MOD - 2) % MOD;
}

int f[N], g[N];
void init(int n) {
    f[0] = 1;
    FOR(i, 1, n) f[i] = mul(f[i - 1], i);
    g[n] = inv(f[n]);
    ROF(i, n - 1, 0) g[i] = mul(g[i + 1], i + 1);
}

int c(int n, int m) {
    if (m > n) return 0;
    return mul(f[n], mul(g[m], g[n - m]));
}

int n;
int a[N];
void solve(int Case) { // printf("Case #%d: ", Case);
    rd(n);
    FOR(i, 1, n) rd(a[i]);

    int aa = INT_MAX;
    FOR(i, 1, n) aa &= a[i];

    int cnt = 0;
    FOR(i, 1, n) if (aa == a[i]) ++cnt;

    debug(aa, cnt);

    int ans = mul(2, mul(c(cnt, 2), f[n - 2]));
    pln(ans);
}

int main() {
#ifdef BACKLIGHT
    freopen("a.in", "r", stdin);
    // freopen("a.out", "w", stdout);
    auto begin = std::chrono::steady_clock::now();
#endif

    init(N - 1);
    // ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    rd(T);
    for (int _ = 1; _ <= T; _++) solve(_);

#ifdef BACKLIGHT
    auto end = std::chrono::steady_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - begin);
    cerr << "\033[32mTime Elasped: " << duration.count() << " ms\033[0m" << endl;
#endif
    return 0;
}
### Prompt

Please formulate 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
#include <bits/stdc++.h>
using namespace std;
 
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using VI = vector<int>;
using VL = vector<ll>;
using VVI = vector<vector<int>>;
using VVL = vector<vector<ll>>;
using PII = pair<int,int>;
using PLL = pair<ll, ll>;
 
#define REP(i, _, __) for (int i = (_); i < (__); ++i)
#define PER(i, _, __) for (int i = (_-1); i >= (__); --i)
#define FOR(i, _, __) for (int i = (_); i <= (__); ++i)
#define ROF(i, _, __) for (int i = (_); i >= (__); --i)
#define FC(v, V) for (const auto& v: V)
#define FE(v, V) for (auto& v: V)

#define EB emplace_back
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(),(x).end()
#define LLA(x) (x).rbegin(),(x).rend()
#define pf printf

const double PI = acos(-1.0);

template<typename T>
T MIN(T a, T b) { return min(a, b); }

template<typename First, typename... Rest>
First MIN(First f, Rest... r) { return min(f, MIN(r...)); }

template<typename T>
T MAX(T a, T b) { return max(a, b); }

template<typename First, typename... Rest>
First MAX(First f, Rest... r) { return max(f, MAX(r...)); }

template<typename T>
inline void umin(T& a, const T& b) { if (a > b) a = b; }

template<typename T>
inline void umax(T& a, const T& b) { if (a < b) a = b; }

ll FIRSTTRUE (ll l, ll r, function<bool(ll)> f) {
    ll res = l - 1, mid;
    while(l <= r) {
        mid = (l + r) >> 1;
        if (f(mid)) r = mid - 1, res = mid;
        else l = mid + 1;
    }
    return res;
}

ll LASTTRUE (ll l, ll r, function<bool(ll)> f) {
    ll res = l - 1, mid;
    while(l <= r) {
        mid = (l + r) >> 1;
        if (f(mid)) l = mid + 1, res = mid;
        else r = mid - 1;
    }
    return res;
}

const int __BUFFER_SIZE__ = 1 << 20;
bool NEOF = 1;
int __top;
char __buf[__BUFFER_SIZE__], *__p1 = __buf, *__p2 = __buf, __stk[996];
inline char nc() {
    return __p1 == __p2 && NEOF && (__p2 = (__p1 = __buf) + fread(__buf, 1, __BUFFER_SIZE__, stdin), __p1 == __p2) ? (NEOF = 0, EOF) : *__p1++;
}

#define rd read
template<typename T>
inline bool read(T &x) {
    char c = nc();
    bool f = 0; x = 0;
    while (!isdigit(c)) c == '-' && (f = 1), c = nc();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = nc();
    if (f) x = -x;
    return NEOF;
}

inline bool need(char c) { return (c != '\n') && (c != ' '); }

inline bool read(char& a) {
    while ((a = nc()) && need(a) && NEOF) ;
    return NEOF;
}

inline bool read(char *a) {
    while ((*a = nc()) && need(*a) && NEOF) ++a; 
    *a = '\0';
    return NEOF;
}

inline bool read(double &x) {
    bool f = 0; char c = nc(); x = 0;
    while (!isdigit(c))  { f |= (c == '-'); c = nc(); }
    while (isdigit(c)) { x = x * 10.0 + (c ^ 48); c = nc(); }
    if (c == '.') {
        double temp = 1; c = nc();
        while (isdigit(c)) { temp = temp / 10.0; x = x + temp * (c ^ 48); c = nc(); }
    }
    if (f) x = -x;
    return NEOF;
}

template<typename First, typename... Rest>
inline bool read(First &f, Rest &... r) {
    read(f);
    return read(r...);
}

#define pr print
#define pln println
template<typename T>
inline void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x == 0) { putchar('0'); return; }
    __top = 0;
    while(x) {
        __stk[++__top] = x % 10 + '0';
        x /= 10;
    }
    while(__top) {
        putchar(__stk[__top]);
        --__top;
    }
}

template<typename First, typename... Rest>
inline void print(First f, Rest... r) {
    print(f); putchar(' ');
    print(r...);
}

template<typename T>
inline void println(T x) {
    print(x); 
    putchar('\n');
}

template<typename First, typename... Rest>
inline void println(First f, Rest... r) {
    print(f); putchar(' ');
    println(r...);
}

template<typename T>
void println(const vector<T>& V) {
    for(const auto& v: V) print(v), putchar(' ');
    putchar('\n');
}

#ifdef BACKLIGHT
#include "debug.h"
#else
#define debug(...)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) { return l + rng() % (r - l + 1); }

const int N = 5e5 + 5;
const int M = 3e6 + 5;
const int K = 1e7 + 5;
const int MOD = 1e9 + 7;              // 998244353 1e9 + 7
const int INF = 0x3f3f3f3f;             // 1e9 + 7 0x3f3f3f3f
const ll LLINF = 0x3f3f3f3f3f3f3f3f;    // 1e18 + 9 0x3f3f3f3f3f3f3f3f
const double eps = 1e-8;

ll qp(ll a, ll b, ll p = MOD) { ll r = 1; while(b) { if (b & 1) r = r * a % p; a = a * a % p; b>>= 1; } return r; }
ll inv(ll a) { return qp(a, MOD - 2); }

int add(int x, int y) {
    return x + y >= MOD ? x + y - MOD : x + y;
}
int mul(int x, int y) {
    return 1ll * x * y % MOD;
}
int sub(int x, int y) {
    return x - y < 0 ? x - y + MOD : x - y;
}
int dvd(int x, int y) {
    return 1ll * x * qp(y, MOD - 2) % MOD;
}

int f[N], g[N];
void init(int n) {
    f[0] = 1;
    FOR(i, 1, n) f[i] = mul(f[i - 1], i);
    g[n] = inv(f[n]);
    ROF(i, n - 1, 0) g[i] = mul(g[i + 1], i + 1);
}

int c(int n, int m) {
    if (m > n) return 0;
    return mul(f[n], mul(g[m], g[n - m]));
}

int n;
int a[N];
void solve(int Case) { // printf("Case #%d: ", Case);
    rd(n);
    FOR(i, 1, n) rd(a[i]);

    int aa = INT_MAX;
    FOR(i, 1, n) aa &= a[i];

    int cnt = 0;
    FOR(i, 1, n) if (aa == a[i]) ++cnt;

    debug(aa, cnt);

    int ans = mul(2, mul(c(cnt, 2), f[n - 2]));
    pln(ans);
}

int main() {
#ifdef BACKLIGHT
    freopen("a.in", "r", stdin);
    // freopen("a.out", "w", stdout);
    auto begin = std::chrono::steady_clock::now();
#endif

    init(N - 1);
    // ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    rd(T);
    for (int _ = 1; _ <= T; _++) solve(_);

#ifdef BACKLIGHT
    auto end = std::chrono::steady_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - begin);
    cerr << "\033[32mTime Elasped: " << duration.count() << " ms\033[0m" << endl;
#endif
    return 0;
}
```