A sequence of n non-negative integers (n ≥ 2) a1, a2, ..., an is called good if for all…
- User
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: denotes the bitwise AND operation.
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.
Assistant
We need to count permutations p such that for all i from 1 to n-1, AND of first i equals AND of last n-i.
Define sequence b_i = a_{p_i}. Condition: For all i, AND_{j=1}^i b_j = AND_{j=i+1}^n b_j.
We need to count permutations of indices (i.e., order of given numbers) such that condition holds.
Observation: This condition is symmetric; if we reverse the permutation, condition still holds? Let's check: If a permutation satisfies condition, then for reversed sequence, for i, left AND becomes original right AND? Not sure, but maybe the condition forces the sequence to be such that the AND of entire array is same as each side? Let's analyze.
Let total AND: X = AND_{j=1}^n a_j. Note that AND over all numbers is X. For any partition, left AND and right AND are both >= X? Actually AND of subset is always >= X? Since AND over all gives the bits that are 1 in all numbers; any subset's AND may have more bits 1? Wait, AND over subset yields bits that are 1 in all elements of that subset; since all elements of entire set have bits in X as 1, any subset also have those bits 1 because each element has them? Actually if X has a bit set to 1, then all numbers have that bit=1, so any subset also all have that bit=1, so the AND of subset will have that bit=1. So AND of subset is >= X (i.e., superset of bits). So left AND and right AND both have all bits of X set. So they are at least X.
Now condition requires left AND = right AND for each i. Let's denote L_i = AND_{j=1}^i b_j, R_i = AND_{j=i+1}^n b_j. Condition: L_i = R_i for all i.
Consider i=1: b_1 = AND_{j=2}^n b_j. So b_1 equals the AND of all other elements. Similarly, i=n-1: AND_{j=1}^{n-1} b_j = b_n.
Thus b_1 = AND(b_2,...,b_n) and b_n = AND(b_1,...,b_{n-1}). Combined with total AND X = b_1 & b_2 & ... & b_n = b_1 & (AND others) = b_1 & b_1 = b_1? Wait careful: total AND X = b_1 & (AND_{j=2}^n b_j). But condition says b_1 = AND_{j=2}^n b_j. So then X = b_1 & b_1 = b_1. So b_1 = X. Similarly, X = AND_{j=1}^{n-1} b_j & b_n = b_n & b_n = b_n, so b_n = X. So the first and last elements must equal X, the overall AND of all numbers.
Now consider i=2: L_2 = b_1 & b_2, R_2 = AND_{j=3}^n b_j. Condition: b_1 & b_2 = AND_{j=3}^n b_j. But we know b_1 = X. So X & b_2 = AND_{j=3}^n b_j. Also note that AND_{j=3}^n b_j = (AND_{j=2}^n b_j) & (b_2?) Wait: AND_{j=3}^n b_j = (AND_{j=2}^n b_j) with b_2 removed? Actually AND_{j=2}^n b_j = b_2 & AND_{j=3}^n b_j. But from i=1 we have b_1 = AND_{j=2}^n b_j => X = AND_{j=2}^n b_j. So AND_{j=2}^n b_j = X. Then X = b_2 & (AND_{j=3}^n b_j). So AND_{j=3}^n b_j = X / b_2? Not division; it's the value such that b_2 & that = X. Since X is subset of bits of b_2 (bits where b_2 has 0? Actually if b_2 has a bit 1, then AND with something to yield X: that something must have that bit equal to X's bit; if b_2 has bit 0, then regardless of that something, the AND will have 0; so for bits where b_2 is 0, X must be 0. Since X = AND all numbers, that's true: for any bit where any number has 0, X has 0. So b_2 may have bits 1 that are not in X? Possibly, but if b_2 has a bit 1 that is not in X, then to have b_2 & (AND_{j=3}^n) = X, that bit must be 0 in AND_{j=3}^n, because otherwise the AND would have that bit 1. So AND_{j=3}^n must have 0 on those bits. So indeed AND_{j=3}^n = X with possibly extra bits 0? Actually X is the AND of all numbers, so for any bit not in X, at least one number has 0. But that 0 could be among b_2 or among others. So it's plausible.
But we have condition from i=2: X & b_2 = AND_{j=3}^n b_j. But we also have from earlier: X = b_2 & AND_{j=3}^n b_j. So those two equations are symmetric. Actually both are equivalent? Let's check: From total: X = b_2 & AND_{j=3}^n b_j. From i=2: X & b_2 = AND_{j=3}^n b_j. So we have:
(1) X = b_2 & Y, where Y = AND_{j=3}^n b_j. (2) X & b_2 = Y.
Combine: Y = X & b_2. Plug into (1): X = b_2 & (X & b_2) = (b_2 & X) because b_2 & (X & b_2) = X & b_2 (since b_2 & b_2 = b_2). So X = X & b_2. That means X is a subset of b_2 bits: i.e., all bits set in X must be set in b_2, and b_2 may have extra bits. But from X = b_2 & Y, if X = X & b_2, then indeed that is true. Actually equation X = X & b_2 implies that wherever X has 1, b_2 must have 1. So b_2 has at least the bits of X. Is that already true? Since X is AND of all numbers, for each number, if X has bit 1, all numbers have that bit 1, so b_2 must have that bit 1. So indeed b_2 already must have all bits of X, because X's 1 bits are common to all numbers. So condition X = X & b_2 holds automatically. So i=2 condition doesn't impose extra constraints beyond b_2 having X bits, which is true for all numbers? Wait: For any number a_i, does it necessarily have all bits of X? Since X = AND of all numbers, any bit that is 1 in X is 1 in every number. So yes, every number has all bits of X. So for any element b_j, we have b_j contains X (i.e., X & b_j = X, or equivalently X is subset of b_j). So the condition from i=2 yields automatically? Let's verify more systematically.
We derived that from i=1 we got b_1 = X and b_n = X. Then we also have that for all i, L_i = R_i. We might be able to characterize the entire sequence.
Observe that condition is reminiscent of "palindromic AND sequence": L_i = R_i for all i. Consider the total AND X. For any i, L_i & R_i = X, because AND of all numbers = L_i & R_i = X. Since L_i = R_i, we have L_i = R_i = some value Y_i, and then Y_i & Y_i = Y_i = X? Wait: L_i & R_i = X, and if L_i = R_i = Y, then Y & Y = Y = X, so Y must equal X. Because Y & Y = Y. So we get L_i = R_i = X for all i! Let's verify: Indeed, for any i, we have total AND = L_i & R_i = X. But condition says L_i = R_i. So let common value = V. Then V & V = V = X. So V = X. Therefore, for all i, AND of first i equals X, and AND of last n-i equals X. So the condition is equivalent to: For every prefix (of length i), its AND equals X, and for every suffix (of length n-i), its AND equals X.
But is this equivalent to the original condition? Let's check: Original condition says L_i = R_i. We have L_i & R_i = X. If L_i = R_i = V, then V & V = V, so V = X. So indeed L_i = R_i = X. So condition forces that all prefix ANDs and suffix ANDs equal total AND X.
Conversely, if all prefix ANDs equal X and all suffix ANDs equal X, then obviously L_i = R_i = X, so condition holds.
Thus the condition is: For the permuted sequence b_1..b_n,
- AND(b_1,...,b_i) = X for all i from 1 to n-1 (since i=n gives total X automatically)
- AND(b_{i+1},...,b_n) = X for all i from 1 to n-1 (equivalently all suffixes of length >=1 have AND X).
But note that if all prefixes (including maybe i=1) have AND = X, then b_1 = X. Similarly, suffix of length 1 gives b_n = X. Also for i from 2 to n-1, the prefix AND must stay X. That means adding elements after the first does not change the AND from X; i.e., the AND of all numbers is X, and the AND of the first i remains X, which means that each subsequent element must have all bits that are 1 in X set (which is already true) but also must not introduce new bits that would cause the AND to drop? Actually AND of set is intersection of bits that are 1 in all elements. Starting with b_1 = X. For AND to remain X after adding b_2, we need b_1 & b_2 = X. Since b_1 = X, this requires X & b_2 = X, i.e., X is subset of b_2 (X bits are 1 in b_2) which holds for any b_2 as argued. But wait: X & b_2 = X means that wherever X has 1, b_2 has 1. That's true for all numbers because X is AND of all numbers. But could adding b_2 cause the AND to become something smaller than X? No, AND can only clear bits (set bits to 0) if some element lacks that bit. Since b_1 = X already has all bits of X 1; if b_2 lacks any bit that is 1 in X, then X would have that bit 1, but b_2 lacking it would cause AND to have 0 for that bit, resulting in something less than X. But we argued all numbers have all bits of X, because X is AND of all numbers. So indeed any element b_j must have all bits of X as 1. So b_2 automatically satisfies X & b_2 = X. So prefix AND stays X after adding any element? Let's test: Suppose we have numbers: X = 4 (100), and other numbers could be 5 (101) or 6 (110) etc, all have bit 2 (value 4) set. If we take b_1 = 4, b_2 = 5 => b_1 & b_2 = 4 & 5 = 4 (since 5=101, 4=100 -> 100) => X. So yes stays X. b_1=4, b_2=6 => 4 & 6 = 4 (110 & 100 = 100) => X. In fact, AND of X with any number that contains X as a subset yields X. So indeed, if b_1 = X, then for any subsequent numbers that all contain X (which they do, because they are from the set and overall AND is X, so each has bits of X set), the AND of the prefix will remain X. That is, once we have placed X at the first position, the prefix AND for any i will be X, because X & any superset = X.
But careful: The condition also requires that suffixes AND equal X. Similarly, if b_n = X, then suffix AND from any i will be X as long as all numbers contain X? Let's examine suffix: For suffix starting at position i+1, we need AND of b_{i+1}...b_n = X. If the last element is X, then the suffix AND of the whole last part is the AND of a set of numbers each containing X, and ending with X, so it's also X? Actually the AND of a set of numbers, each containing X, will be at least X. But it could be greater than X if all numbers have extra bits in common beyond X. But if the set includes X itself, then the AND will be exactly X because X has only the common bits, and any extra common bits would require all numbers to have those bits set, but X itself lacks them, so they cannot be common. More formally: If the set contains an element equal to X, then AND over the set cannot have any bit not set in X, because that element X has 0 there. So the AND is exactly X. So if the last element is X, then for any suffix that includes that last element (i.e., all suffixes except the empty one), the AND will be X because the presence of X forces the AND to be exactly X. Similarly, for prefixes, if the first element is X, then all prefixes that include the first element will have AND = X. But our condition requires all prefixes (including i=1) to have AND = X, so first element must be X. And all suffixes (including i=n-1) require AND = X, so last element must be X. Also for prefixes of length >1 that don't include the first? Actually all prefixes include first element. So if first element is X, then prefix AND always X regardless of the rest. Similarly, if last element is X, then suffix AND always X regardless of the rest, as long as the suffix includes the last element. But does suffix of length 1 (i=n-1) include last element? Yes it is just b_n, which is X. Suffix of length 2 includes b_{n-1} and b_n; AND = b_{n-1} & X. Since b_{n-1} contains X (has all X bits), b_{n-1} & X = X (because X is subset of b_{n-1}, but also X might have bits 0 where b_{n-1} may have 1? Actually b_{n-1} & X = X, because X's bits are 1 only where both have 1; any extra 1s in b_{n-1} are zero in X, so result is X. So indeed AND = X. By induction, any nonempty set of numbers all containing X, and containing X itself, yields AND = X. So the condition reduces to: The first element must be X, and the last element must be X. And nothing else is required? Let's verify with an example from problem: test case 3: array [0,2,0,3,0]. Compute X = AND of all numbers: 0 & 2 = 0, 0&0=0,0&3=0,0&0=0 => X=0. The good permutations counted 36. Total permutations n! = 120. If condition only requires first and last be X=0, then count of permutations with first and last equal to 0. Let's count zeros: numbers: 0,0,0? Actually list: 0,2,0,3,0 -> there are three zeros. So count permutations where first and last are 0. Number of ways: choose first element: must be 0, so pick one of the three zeros. Then choose last element: must be 0 from the remaining zeros: 2 choices. Then arrange the remaining 3 elements (2 non-zero? Actually remaining after picking first and last: we have n-2=3 positions for the remaining 3 numbers (two zeros? Wait we have total three zeros; after picking first and last zeros, we have used two zeros, so remaining numbers: one zero, and two non-zero numbers: 2 and 3. So 3! /? Actually they are distinct? The numbers are not necessarily distinct? They are values; but permutations are of indices, so elements are considered distinct by position even if values same. So we treat each occurrence as distinct. So counting permutations of n distinct items with constraint that the first and last positions are occupied by items that have value X (0). There are cnt_X items (count of indices where a_i = X). So number of permutations where first and last are among those: choose one of cnt_X for first, choose one of (cnt_X-1) for last, then permute remaining (n-2) arbitrarily: (cnt_X)(cnt_X-1)(n-2)!. For n=5, cnt_X=3 => 323! = 6*6=36. That matches output 36. So indeed the count is 36. That suggests condition is exactly that: first element = X and last element = X.
Test case 1: all numbers are 1. X=1. cnt_X = n=3. So permutations with first and last = X. Count = 321! = 6. That matches output 6.
Test case 2: [1,2,3,4,5]. Compute X = 1&2&3&4&5. Let's compute: 1=001,2=010 -> 0, so X=0. cnt_X? How many zeros? None of them are zero (all positive). So cnt_X = number of elements equal to 0? But X=0, but none are 0. So cnt_X=0, then permutations with first and last = 0 is 0. Output 0, matches.
Test case 4: [1,3,5,1]. Compute X = 1&3&5&1 = 1 & 3 =1, 1&5=1, 1&1=1 => X=1. cnt_X: numbers equal to 1: there are two ones. So count = cnt_X*(cnt_X-1)(n-2)! = 212! = 22 =4. Output 4, matches.
Thus the problem reduces to: Let X = AND of all a_i. Count permutations such that first and last elements are equal to X. But need to ensure that this condition is both necessary and sufficient. We argued that if first and last are X, then condition holds (given that all numbers contain X). But is there any additional subtlety? Let's double-check with an example where numbers all contain X but the condition might still fail? Consider numbers: X=2 (binary 10). Suppose numbers: 2, 6 (110), 10 (1010). All contain bit 2? 6=110 includes bit 2 (value 2) yes; 10=1010 includes bit 2? Actually 10 decimal = 1010 binary, bit for 2 is 1? 2^1 =2, yes bit1 is 1, so 10 includes 2. Now X=2. If we set first=2, last=2? But we only have one 2. So need at least two X's for a permutation to have first and last both X. But if we have two X's? Let's create an example with cnt_X >=2. Example: numbers: 2,2,6,10. X=2. Permutation: [2,6,10,2] (first=2, last=2). Check condition: L1 = 2, R1 = AND(6,10,2) = 6&10=2? 6=110,10=1010 => 6&10 = 2? 6 decimal: 0110, 10:1010, AND=0010=2, &2=2 => 2. So L1=2=R1. L2=2&6=2, R2=10&2=2 => good. L3=2&6&10=2, R3=2 => good. Works. What about [2,10,6,2]? L1=2, R1=10&6&2 = 10&6=2, &2=2 => ok. L2=2&10=2, R2=6&2=2 => ok. L3=2&10&6=2, R3=2 => ok. So seems fine.
What if we have numbers that all contain X but we don't have X as first or last? The condition fails because we derived b_1 and b_n must be X. So necessity is proven: from i=1 and i=n-1 we got b_1 = X and b_n = X. So condition forces first and last to be X. So sufficiency: if first and last are X, then for any i, prefix AND = X because first element is X, and AND of X with any numbers containing X is X. Similarly suffix AND = X because last element is X. So L_i = R_i = X for all i. So condition holds. So indeed condition is equivalent to: first and last elements are both equal to the overall AND X.
Thus the problem reduces to counting permutations of n distinct items (with possibly duplicate values but items are distinct by index) such that the first position and the last position are both occupied by elements whose value equals X.
Let cnt = number of indices i such that a_i == X. Then if cnt < 2, answer = 0. Otherwise, count = P(cnt,2) * (n-2)! because we choose two distinct indices among the cnt to place at first and last (order matters: first and last are distinct positions, so we assign one of the chosen to first, the other to last; that's cnt * (cnt-1) ways), and then arrange the remaining n-2 elements arbitrarily in the middle (n-2)! ways. Since items are distinct, all permutations of remaining are distinct.
But we must be careful about modulo and large n, but that's straightforward.
Now check if there is any other nuance: What about the case where n=2? Then first and last are the only two positions. Then condition requires both elements equal X. So both must be X. So if cnt >=2, then number of permutations = number of ways to assign two distinct X's to the two positions: cnt*(cnt-1). And (n-2)! = 0! =1. So formula works.
Also check scenario where some elements might not contain X? Actually by definition of X = AND of all numbers, every number must contain X bits? Wait: X = AND of all numbers; this means for any bit position, if X has 1, then all numbers have 1 at that bit. So yes, every number has all bits of X set; i.e., a_i & X = X for all i. But does that imply a_i >= X? Yes, but a_i may not equal X; they could be larger. So condition that all numbers contain X is automatically true. So sufficiency argument holds.
Thus answer is simple.
We should verify with some more examples manually:
Case: n=3, a=[0,0,1]. X = 0&0&1 = 0. cnt_X = number of zeros = 2. Then answer = 21(1)! = 2. Permutations: indices: two zeros (A,B) and one (C) with 1. Good permutations must have first and last = 0. So possible sequences: 0 (A),1,0 (B) and 0 (B),1,0 (A) -> 2. Check condition: For [0,1,0], L1=0, R1=1&0=0 -> ok; L2=0&1=0, R2=0 -> ok. So works. What about [0,0,1]? First=0, last=1 not 0 -> fails. Good.
Case: n=3, a=[2,2,2]. X=2, cnt=3, answer=321=6, which is n! since all permutations good? Actually condition requires first and last =2, but all numbers are 2, so any permutation satisfies first and last =2 automatically. So all 6 permutations good. That matches.
Case: n=4, a=[1,1,2,3]. X = 1&1&2&3 = 1&2=0? 1=001,2=010 -> 0. So X=0. cnt_X = number of zeros? None? All numbers are positive? 1,1,2,3 all >0, so cnt_X=0, answer=0. Let's test maybe there is a good permutation? Try order: [1,1,2,3] check: L1=1, R1=1&2&3=1&2=0? Actually 1&2=0, so R1=0. Not equal. So fails. Any? Probably none.
Case: n=4, a=[0,0,0,1]. X=0, cnt=3, answer=322! = 62=12? Actually 32=6, (4-2)!=2!=2, total 12. Total permutations 24, so half? Let's test: Must have first and last zeros. With three zeros (A,B,C) and one 1 (D). Number of permutations with first and last zeros: choose first zero: 3, last zero: 2, then arrange middle two: D plus the remaining zero (since we used two zeros, one zero left). So middle two can be arranged in 2! ways (zero and D). So 322 =12. Good.
Now check condition manually for a case that might break: Suppose numbers: [X, y, z] where y and z contain X but maybe y & z has bits beyond X? But AND with X later? Actually prefix AND with first X always X. Suffix AND with last X always X. So condition holds. So all good.
Thus solution is straightforward.
But careful: Are there any corner cases where X is such that some numbers do not contain X? That can't happen because X is AND of all numbers, so for any bit set in X, all numbers have that bit set. So each number has at least those bits. So yes.
Edge: When cnt >= 2, answer = cnt * (cnt - 1) % MOD * factorial(n-2) % MOD. Compute factorials up to max n across test cases (2e5). Precompute factorials modulo MOD.
Complexities: O(n total) to compute X and count cnt. Then answer using precomputed factorial.
We must also handle large t, sum n <= 2e5. So precompute factorial array up to 200000.
Now verify with sample: Already matches.
But wait, test case 2: X=0, cnt=0 => answer=0. Good.
Thus solution is simple.
But is there any trick if numbers are identical? That's covered.
Potential pitfalls: Need to compute overall AND correctly. Also note that a_i can be up to 1e9, but bitwise AND works fine.
Thus implement:
For each test case:
- read n, list a.
- compute X = a[0]; for i in 1..n-1: X &= a[i].
- count cnt = number of a_i == X.
- if cnt < 2: answer = 0.
- else: answer = cnt * (cnt-1) % MOD * fact[n-2] % MOD.
- output answer.
Precompute fact[0..200000] with fact[0]=1, fact[i]=fact[i-1]*i % MOD.
That's it.
But let's double-check derivation thoroughly because the original condition is L_i = R_i, and we concluded L_i=R_i=X. We used property L_i & R_i = X, which is true because total AND = X. However careful: For i from 1 to n-1, L_i and R_i are ANDs of disjoint nonempty sets covering all elements, so total AND = L_i & R_i. So indeed L_i & R_i = X. If L_i = R_i = V, then V & V = V, so V = X. So that part is solid. So L_i = R_i = X for all i. Therefore the condition is equivalent to L_i = X and R_i = X for all i. That is stronger than just first and last = X? Let's see: L_i = X for all i implies prefix AND is always X. Starting with i=1 gives b_1 = X. For i=2, b_1 & b_2 = X, but since b_1 = X, we get X & b_2 = X, which is always true if b_2 contains X bits. But is it always true? Yes, because b_2 has X bits, X & b_2 = X. So no extra constraint on b_2. Similarly for any i, as long as b_1 = X and all numbers contain X, prefix AND remains X. So the only necessary condition from prefix side is b_1 = X. Similarly, from suffix side, b_n = X is necessary. So indeed condition reduces to b_1 = X and b_n = X.
But we must ensure that for the prefix condition to hold for all i, we only need b_1 = X. Because after that, the AND stays X regardless of others. But is there any scenario where b_1 = X but some later prefix AND might become something not equal to X? Let's check: Suppose b_1 = X. Then L_2 = X & b_2. Since b_2 contains X bits (because overall AND X means all numbers have those bits), X & b_2 = X. Indeed if X has bit 1, b_2 has 1, so AND yields 1; if X has bit 0, then b_2 may have either 0 or 1, but X has 0, so AND yields 0. So result is exactly X. Because X & b_2 gives bits where both have 1; X's 1 bits are present in b_2, so they remain 1; X's 0 bits yield 0 regardless of b_2. So L_2 = X. Then L_3 = L_2 & b_3 = X & b_3 = X, and so on. So prefix AND stays X. So b_1 = X suffices.
Similarly, suffix: b_n = X ensures all suffix ANDs are X, because starting from the end, AND with numbers that contain X and include X itself yields X.
Thus the condition is exactly that.
One more nuance: We used the property that all numbers contain X. That's true. So sufficiency holds.
Thus answer is as described.
Now we just need to code.
But careful: In counting permutations, we treat each occurrence as distinct. However, if there are duplicate values but not equal to X, it doesn't matter because they are distinct indices. The formula cnt*(cnt-1)*(n-2)! counts permutations of distinct items where first and last positions are filled with two distinct items from the set of cnt items that equal X. This correctly counts each arrangement once because after picking which two X items go to ends (ordered: first and last), the remaining n-2 items (including possibly other X items if cnt>2) are arranged arbitrarily in the middle. This counts all permutations where first and last are X. Since items are distinct, it's correct.
Double-check for duplicates: Example: a = [X, X, X] with n=3. cnt=3. Formula: 32(1)! = 6. All 6 permutations have first and last X? Let's list: items A,B,C all X. Permutations: (A,B,C): first A X, last C X -> good. (A,C,B): first A X, last B X -> good. (B,A,C): first B X, last C X -> good. (B,C,A): first B X, last A X -> good. (C,A,B): first C X, last B X -> good. (C,B,A): first C X, last A X -> good. All good. So matches.
If cnt>2, middle may contain X as well, which is fine.
Thus solution stands.
Now we should consider whether there is any scenario where X is something and cnt >= 2 but the condition fails because some element does not contain X? Impossible.
Therefore implement.
But I recall some Codeforces problem "Good Sequence" or "AND Sequences" that had similar idea, and answer was cnt*(cnt-1)*(n-2)! if cnt>=2 else 0.
Check memory: Precompute factorials up to 2e5.
Edge Cases: n=2, cnt=2 -> answer = 210! = 2. List: both items X, permutations: [X1,X2] and [X2,X1], both good? Check condition: L1 = first, R1 = second; they must be equal => both X, and they are both X, so OK. Also total AND X = X1 & X2 = X? Since both are X, AND = X. So condition holds. So answer 2. Good.
n=2, cnt=1 -> answer 0. Indeed if only one X, cannot have both ends X.
So final solution.
Now we produce Python code.
But we need to handle up to 2e5 total n. Precompute factorial array once.
Implementation steps:
- MOD = 10**9+7
- Read t.
- Precompute factorial up to max_n = 200000 (or we can compute per test case using precomputed list, but we need to know max n across tests; we can either precompute to 200000 (since sum n <=200000, but individual n can be up to 200000, so we need factorial up to 200000 anyway). So precompute fact = [1]*(max_n+1) for i in 1..max_n: fact[i] = fact[i-1]*i % MOD.
- For each test:
- n = int(input())
- a = list(map(int, input().split()))
- X = a[0]
- for val in a[1:]: X &= val
- cnt = sum(1 for val in a if val == X)
- if cnt < 2: ans = 0 else: ans = cnt * (cnt-1) % MOD ans = ans * fact[n-2] % MOD
- print(ans)
But need to ensure factorial for n-2 where n could be 2 => fact[0] exists. So precompute up to 200000.
Check sum of n: we can precompute factorial up to 200000 (since max n per test case is 2e5, and sum of n also 2e5, so that's fine). We can also compute factorial on the fly using loop up to max_n overall.
Complexity O(total n).
Now let's think about proof for clarity: Already reasoned.
Thus solution is trivial.
But wait: There is a nuance: In condition for i from 1 to n-1, L_i = R_i, we derived L_i = R_i = X. But is it possible that L_i = R_i but not equal to X? Since L_i & R_i = X, if L_i = R_i = V, then V & V = V => V = X. So yes, must equal X.
Thus correct.
Potential pitfalls: integer overflow, but Python handles.
Now just code.
But before finalizing, test with random small cases via brute force to confirm.
We'll write a small brute for n <= 5 and random values, compare formula.
But since it's reasoning, but let's do mental test:
Case: n=3, values: [2,3,6]. X = 2&3&6 = 2 (10) & 3 (11) = 2 (10) & 6 (110) = 2? 2&6 = 2. So X=2. cnt = number of 2's: only a1=2, so cnt=1 <2 => answer 0. Brute: Permutations? [2,3,6]: L1=2, R1=3&6=2 (3&6=2) => good? 2=2 ok. L2=2&3=2, R2=6 => 2 vs 6? Not equal. So fails. [2,6,3]: L1=2, R1=6&3=2 => ok. L2=2&6=2, R2=3 => 2 vs 3 fail. [3,2,6]: L1=3, R1=2&6=2 => 3 vs 2 fail. [3,6,2]: L1=3, R1=6&2=2 fail. [6,2,3]: L1=6, R1=2&3=2 fail. [6,3,2]: L1=6,R1=3&2=2 fail. So indeed 0 good. Good.
Case: n=3, values: [2,2,6]. X=2&2&6=2. cnt=2 (two 2's). answer = 211! = 2. Permutations: (2a,2b,6): first=2, last=6 not 2? Actually last=6 not 2, fails because last must be X? But we claim only first and last need be X. In this permutation, last=6, so fails. But does condition hold? Check: L1=2, R1=2&6=2? 2&6=2 -> ok. L2=2&2=2, R2=6 -> 2 vs 6 fail. So fails. (2a,6,2b): first=2, last=2 -> good? Check: L1=2, R1=6&2=2 ok; L2=2&6=2, R2=2 ok -> good. (2b,2a,6): first=2, last=6 fails; (2b,6,2a): good; (6,2a,2b): first=6 fails; (6,2b,2a): first=6 fails. So exactly 2 good. matches.
Case: n=4, values: [2,2,2,6]. X=2. cnt=3. answer=322! = 6*2=12. Total permutations 24, so 12 good. We'll test a few: Good ones must have first and last =2. So number: pick first 2: 3 choices, last 2: 2 choices, arrange middle two: they are (remaining 2, and 6) in 2! =2 orders => 12. Condition holds? For any such arrangement, we need to verify: first=2, last=2. prefix AND: after first 2, then & second =2& something: if second is 2, stays 2; if second is 6, 2&6=2. So prefix stays 2. suffix: last 2, previous & last: if previous is 2, 2&2=2; if previous is 6, 6&2=2. So suffix stays 2. So condition holds. So 12 good. Good.
Thus solution stands.
Now edge: what if X=0, and some numbers are 0? Yes, works.
One more nuance: Is it possible that cnt >=2 but condition fails because some element does not contain X? As argued impossible. So final.
Thus answer is straightforward.
Now we should consider time constraints: t up to 1e4, sum n up to 2e5, so O(total n) is fine.
Now produce final answer.
But wait: the problem statement says "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}, ... is good." Since a_i can be large, but we use values.
Thus solution as above.
Let's double-check the derivation of necessity: From i=1: a_{p1} = AND of rest -> thus b1 = AND(b2..bn) => then total AND = b1 & (AND(b2..bn)) = b1 & b1 = b1 => b1 = X. Similarly i=n-1 gives bn = X. So first and last must be X. So count = permutations with first and last from set of indices where value equals X. So answer formula.
Thus we can implement.
But careful: The condition i=1 gives b1 = AND(b2..bn). Since b1 = X, and X is AND of all, then automatically AND(b2..bn) = X? Actually from total AND = X = b1 & AND(b2..bn) = X & AND(b2..bn) => So AND(b2..bn) must be a number such that X & that = X. This implies that AND(b2..bn) has at least the bits of X (i.e., X is subset of that number). But also from b1 = X and condition b1 = AND(b2..bn) we get AND(b2..bn) = X. So consistent. So yes.
Now for i=n-1, we get bn = X.
Thus the necessity is solid.
Now we need to ensure that the condition for intermediate i is automatically satisfied if first and last are X. We argued that prefix AND stays X because b1=X and all numbers contain X. However, is it possible that the prefix AND could become something else? Consider b1 = X, b2 = some number that has all bits of X, but also maybe b2 has extra bits. Then X & b2 = X. So L2 = X. Inductively L_i = X for all i. Similarly suffix. So yes.
Thus sufficiency holds.
Hence answer is as above.
Now we produce final solution.
But wait: There might be an alternative interpretation: The condition must hold for all i from 1 to n-1, not just first and last. We proved it's equivalent, so fine.
Now let's consider if the array contains numbers that are not distinct; but we treat indices distinct.
Thus code.
Potential pitfalls: In Python, reading input fast for large t. Use sys.stdin.read or sys.stdin.buffer.
We'll implement:
import sys
MOD = 10**9+7 MAXN = 200000
fact = [1]*(MAXN+1) for i in range(1, MAXN+1): fact[i] = fact[i-1]*i % MOD
def solve(): import sys data = sys.stdin.buffer.read().split() it = iter(data) t = int(next(it)) out = [] for _ in range(t): n = int(next(it)) a = [int(next(it)) for _ in range(n)] X = a[0] for val in a[1:]: X &= val cnt = sum(1 for val in a if val == X) if cnt < 2: out.append('0') else: ans = cnt * (cnt - 1) % MOD ans = ans * fact[n-2] % MOD out.append(str(ans)) sys.stdout.write('\n'.join(out))
if name == 'main': solve()
Now test with given sample.
Will output correct.
Thus final answer.
But let's double-check large n: factorial precomputed up to 200000; n-2 up to 199998, fine.
Now check that we accounted for modulo.
Now done.
However, before concluding, let's think about possibility of overflow in intermediate multiplication: cnt can be up to n <= 2e5, so cnt*(cnt-1) up to 4e10, within Python int, but modulo we do mod anyway.
Now, some people might think about the case where X is not necessarily present as an element? But from condition we derived b1 = X, so X must appear at least once? Actually b1 is an element of the array, so X must be present as an element. But wait, is it forced that X is present as an element? From condition b1 = X, and b1 is some a_i, so X must be equal to some a_i. So if X is not present in the array, then no permutation can satisfy condition. Our formula gives cnt=0 => answer 0. That matches.
Thus all good.
Now I'll produce final answer. ```python
import sys
MOD = 10**9 + 7 MAXN = 200_000
pre‑compute factorials modulo MOD
fact = [1] * (MAXN + 1) for i in range(1, MAXN + 1): fact[i] = fact[i - 1] * i % MOD
def solve() -> None: data = sys.stdin.buffer.read().split() it = iter(data) t = int(next(it)) out_lines = [] for _ in range(t): n = int(next(it)) a = [int(next(it)) for _ in range(n)]
# overall AND total_and = a[0] for x in a[1:]: total_and &= x # count elements equal to total_and cnt = sum(1 for x in a if x == total_and) if cnt < 2: out_lines.append('0') else: ans = cnt * (cnt - 1) % MOD # choose first and last ans = ans * fact[n - 2] % MOD # arrange the middle out_lines.append(str(ans)) sys.stdout.write('\n'.join(out_lines))if name == 'main': solve()