A sequence of integers is said to be beautiful if the bitwise AND, OR, and XOR of its elements are pairwise equal to each other.
You are given a sequence \(A\) of size \(N\). Find the number of non-empty subsequences of \(A\) that are beautiful. Print the answer modulo \(10^9 + 7\).
Input format
- The first line contains an integer \(N\) representing the number of elements in the sequence.
- The second line contains \(N\) space-separated integers \(A_1,\ A_2,\ ...,\ A_N\) representing the sequence.
Output format
In a single line, print the number of non-empty subsequences of \(A\) that are beautiful.
Constraints
\(1 \leq N \leq 2 \cdot 10^5\\ 0 \leq A_i \leq 10^{9}\)
Here the subsequence $$\{A_1,A_3,A_5\}$$ is not beautiful. This is because:
$$A_1 \& A_3 \& A_5 = 1 \& 2 \& 2 = 0$$
$$A_1 | A_3 | A_5 = 1 | 2 | 2 = 3$$
$$A_1 ⊕ A_3 ⊕ A_5 = 1 ⊕ 2 ⊕ 2 = 1$$
For a subsequence to be beautiful, these three values should be equal to each other.
($$\&$$ represents bitwise AND, $$|$$ represents bitwise OR, $$⊕$$ represents bitwise XOR)
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor