AND Sequences

一个 $n$ 个数的非负数组如果 $\forall i\in\left[1,n\right)$ ，有 $a_1$ & $a_2$ & $……$ & $a_i = a_{i+1}$ & $a_{i+2}$ & $……$ & $a_n$ ，那么这个数组叫做 $“$ 好的数组 $”$ 。其中&表示按位与。 给定一个长度为 $n$ 的数组，求这个数组有多少种排列是 $“$ 好的数组 $”$ 。因为这个数字可能很大，所以输出结果模 $10^9+7$ 即可。 两个排列不同，指这个排列有一个位置的数与其他排列的这一位置的数的下表不同。 例如： 如果原数组是 $1,1$ ，那么这个数组有 $2$ 个排列； 如果原数组是 $1,1,1$ ，那么这个数组有 $6$ 个排列。 **输入格式** 第一行输入一个整数 $t\left(1\le t\le10^4\right)$ ，表示数据组数。 每一组数据包含两行，第一行输入一个整数 $n\left(1\le\sum n\le2\times10^5\right)$ ，表示数组大小；第二行输入 $n$ 个整数 $a_1,a_2,……,a_n\left(1\le a_i\le10^9\right)$ ，表示数组中的数。 **输出格式** 对于每一组数据，输出 $1$ 个整数有多少种排列是 $“$ 好的数组 $”$ 。

A sequence of $ n $ non-negative integers ( $ n \ge 2 $ ) $ a_1, a_2, \dots, a_n $ is called good if for all $ i $ from $ 1 $ to $ n-1 $ the following condition holds true: $ $$$a_1 \: \& \: a_2 \: \& \: \dots \: \& \: a_i = a_{i+1} \: \& \: a_{i+2} \: \& \: \dots \: \& \: a_n, $ $ where $ \\&amp; $ denotes the <a href="https://en.wikipedia.org/wiki/Bitwise_operation#AND">bitwise AND operation</a>.</p><p>You are given an array $ a $ of size $ n $ ( $ n \\geq 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$$$.

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ), denoting the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the size of the array. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 10^9 $ ) — the elements of the array. It is guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 2 \cdot 10^5 $ .

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

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

6
0
36
4

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 $ .