Closed Subsets#12414
You are given an array consisting of positive integers
For a non-empty subset of indices S \subseteq \{1,2,\dots,n\}, let be the bitwise AND of all values a_i for i \in S, and let be the bitwise OR of all values a_i for i \in S.
A subset is closed if both of the following conditions hold:
there exists an index i \in S such that a_i = A(S);
there exists an index j \in S such that a_j = O(S).
In other words, the bitwise AND of all elements of the subset must appear as one of the chosen elements, and the bitwise OR of all elements of the subset must also appear as one of the chosen elements.
Your task is to count the number of closed non-empty subsets of the array modulo .
The first line of the test case contains one integer (1 \le n \le 10^{5}) — the number of elements in
The second line contains integers a_1, a_2, \dots, a_n (1 \le a_i \le n) — the elements of array .
Print one integer — the number of non-empty subsets of the array that are closed, modulo .
Example 1
In the sample test case, the closed subsets are exactly \{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{1,3\}, \{2,3\}, \{1,5\}, \{4,5\}.
Subtask ( points): (n \le 18)
Subtask ( points): (n \le 2000)
Subtask ( points): (n \le 10^{4})
Subtask ( points): (n \le 5 \cdot 10^{4})
Subtask ( points): No additional constraints