B. AND Sequences
bitmasks; combinatorics; constructive algorithms; math
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 \)\&\( denotes the bitwise AND operation.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\).
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\).