CF1513B AND Sequences

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