Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

Jzzhu have n non-negative integers a1, a2, ..., an. We will call a sequence of indexes…

  1. User

    Jzzhu have n non-negative integers a1, a2, ..., an. We will call a sequence of indexes i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ n) a group of size k.

    Jzzhu wonders, how many groups exists such that ai1 & ai2 & ... & aik = 0 (1 ≤ k ≤ n)? Help him and print this number modulo 1000000007 (109 + 7). Operation x & y denotes bitwise AND operation of two numbers. Input

    The first line contains a single integer n (1 ≤ n ≤ 106). The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 106).

    Output

    Output a single integer representing the number of required groups modulo 1000000007 (109 + 7).

    Examples

    Input

    3 2 3 3

    Output

    0

    Input

    4 0 1 2 3

    Output

    10

    Input

    6 5 2 0 5 2 1

    Output

    53

  2. DeepSeek Assistant

    We need to count number of non-empty subsets (ordered by index, but subset is just selection of indices) such that bitwise AND of all elements in the subset equals 0.

    We have n up to 1e6, values up to 1e6. Need efficient solution.

    The straightforward O(2^n) is impossible. Need to use inclusion-exclusion over bits, or use principle of counting subsets with AND zero via DP over bits.

    We need to count subsets (any size >=1) such that for all bits (0..20 perhaps since max 10^6 < 2^20 (2^20 = 1048576), so max bits 20) the AND is zero meaning for each bit, at least one selected element has 0 in that bit position.

    So we need number of subsets where for each bit j, the subset is not entirely composed of elements with bit j = 1. In other words, for each bit, avoid subsets where all chosen elements have that bit set. This is like counting subsets that avoid a set of properties: property P_j = "all chosen elements have bit j set". We want subsets where none of these properties hold for any j, i.e., for each bit, at least one element in subset has 0 at that bit.

    So total subsets (non-empty) = 2^n - 1. Want to subtract subsets that violate condition, i.e., there exists at least one bit such that all selected elements have bit=1. Use inclusion-exclusion over bits. Since bits up to 20, we can use inclusion-exclusion over subsets of bits. For each combination of bits S (non-empty subset of bits), we want to count number of subsets (non-empty) such that for all bits in S, all chosen elements have that bit = 1. That is, we count subsets whose elements are all from the set of numbers that have all bits in S set (i.e., numbers that contain S as a subset of their bits). Let’s denote M(S) = number of indices i such that (a_i has all bits in S set) i.e., (a_i & mask(S)) == mask(S). Then number of non-empty subsets consisting only of those elements is 2^{M(S)} - 1. Then by inclusion-exclusion, answer = sum_{S subset of bits, S non-empty} (-1)^{|S|+1} * (2^{M(S)} - 1) ??? Actually careful: we want subsets where for every bit j, at least one element has 0. The complementary subsets are those where there exists at least one bit j such that all elements have 1. Let A_j be the set of subsets (non-empty) where all elements have bit j set. Then we want |complement of union_{j} A_j| = total - |union A_j|. Using inclusion-exclusion:

    |union A_j| = sum_{non-empty S ⊆ bits} (-1)^{|S|+1} |∩_{j∈S} A_j|.

    ∩_{j∈S} A_j = subsets where for all bits in S, all elements have those bits set = all elements belong to the set T(S) = { i : a_i has all bits in S set }. So number of non-empty subsets = 2^{M(S)} - 1. Therefore:

    |union A_j| = sum_{S nonempty} (-1)^{|S|+1} (2^{M(S)} - 1).

    Then desired answer = total non-empty subsets - |union| = (2^n - 1) - sum_{S nonempty} (-1)^{|S|+1} (2^{M(S)} - 1) = (2^n - 1) - [ sum_{S nonempty} (-1)^{|S|+1} 2^{M(S)} - sum_{S nonempty} (-1)^{|S|+1} ].

    Now sum_{S nonempty} (-1)^{|S|+1} =? That's the alternating sum over nonempty subsets. There are 2^m -1 subsets where m is number of bits (max ~20). For each size k, count C(m,k) with sign (-1)^{k+1}. So sum = sum_{k=1..m} (-1)^{k+1} C(m,k) = 1 - sum_{k=0..m} (-1)^k C(m,k) +? Actually sum_{k=0..m} (-1)^k C(m,k) = 0 for m>=1. So sum_{k=1..m} (-1)^{k+1} C(m,k) =? Compute: sum_{k=1}^{m} (-1)^{k+1} C(m,k) = - sum_{k=1}^{m} (-1)^k C(m,k). Since sum_{k=0}^{m} (-1)^k C(m,k) = 0, then sum_{k=1}^{m} (-1)^k C(m,k) = -C(m,0) = -1. So then sum_{k=1}^{m} (-1)^{k+1} C(m,k) = - ( -1 ) = 1? Let's do carefully:

    S0 = Σ_{k=0}^{m} (-1)^k C(m,k) = 0 for m>0.

    Thus Σ_{k=1}^{m} (-1)^k C(m,k) = S0 - C(m,0) = 0 - 1 = -1.

    Then Σ_{k=1}^{m} (-1)^{k+1} C(m,k) = - Σ_{k=1}^{m} (-1)^k C(m,k) = -(-1) = 1.

    So sum_{S nonempty} (-1)^{|S|+1} = 1. But note that each subset S contributes exactly (-1)^{|S|+1}, so the sum is 1 indeed for any m≥1. However, careful: It is sum over all nonempty subsets, not just sizes, but yes it's 1.

    Thus we have:

    Answer = (2^n - 1) - [ Σ_{S≠∅} (-1)^{|S|+1} 2^{M(S)} - 1 ] = (2^n - 1) - Σ_{S≠∅} (-1)^{|S|+1} 2^{M(S)} + 1 = 2^n - Σ_{S≠∅} (-1)^{|S|+1} 2^{M(S)}.

    Wait check: (2^n - 1) - (sum ( (-1)^{|S|+1} 2^{M(S)} ) - 1 )? Actually earlier we had union = sum_{S≠∅} (-1)^{|S|+1} (2^{M(S)} - 1) = sum_{S≠∅} (-1)^{|S|+1} 2^{M(S)} - sum_{S≠∅} (-1)^{|S|+1} = sum_{S≠∅} (-1)^{|S|+1} 2^{M(S)} - 1. So union = (Σ' (-1)^{|S|+1} 2^{M(S)}) - 1.

    Then desired = total - union = (2^n - 1) - [ Σ' (-1)^{|S|+1} 2^{M(S)} - 1 ] = 2^n - Σ' (-1)^{|S|+1} 2^{M(S)}.

    So answer = Σ_{S ⊆ bits} (-1)^{|S|} 2^{M(S)}? Let's check: For S=∅, M(∅) would be number of elements satisfying no condition? Actually for S empty, the condition "all bits in S set" is vacuously true, so M(∅) = n. And (-1)^0 = 1, then term = 2^n. And for non-empty S, we have term with sign (-1)^{|S|}? In expression answer = 2^n - Σ_{S≠∅} (-1)^{|S|+1} 2^{M(S)}. Let's rewrite Σ_{S≠∅} (-1)^{|S|+1} 2^{M(S)} = - Σ_{S≠∅} (-1)^{|S|} 2^{M(S)}. So answer = 2^n - ( - Σ_{S≠∅} (-1)^{|S|} 2^{M(S)} ) = 2^n + Σ_{S≠∅} (-1)^{|S|} 2^{M(S)} = Σ_{S⊆bits} (-1)^{|S|} 2^{M(S)}. Indeed the ∅ term is 2^n. So answer = Σ_{S⊆bits} (-1)^{|S|} 2^{M(S)}. But careful: This sum includes empty set, and we haven't subtracted 1? Let's test with small example: n=1, a=[0]. Bits? 0 is all zeros. M(∅)=1 gives 2^1=2. For any non-empty S, M(S) is number of elements having all bits in S set. For a=0, no element has any bit set, so M(S)=0 for any non-empty S, 2^0=1, sign (-1)^{|S|}. Sum over all non-empty S: sum_{S≠∅} (-1)^{|S|} * 1. For m bits, that sum is? It equals (sum_{k=1..m} (-1)^k C(m,k)) = -1 (since total sum from k=0 is 0, so sum_{k=1} = -C(m,0)= -1). Actually sum_{k=1} (-1)^k C(m,k) = -1. So Σ_{S≠∅} (-1)^{|S|} = -1. Then total Σ_{S} (-1)^{|S|} 2^{M(S)} = 2 + (-1) = 1. Expected answer: subsets with AND 0: only non-empty subset is {1}, AND=0 => count 1. So works.

    Another test: n=3, a=[2,3,3] from example: expected answer 0. Let's compute manually. Bits: up to maybe 2 bits? 2=10,3=11. So bits: maybe consider up to max bit 2? Actually max value 3 uses bits 0 and 1. So m=2. Compute M(S):

    • S empty: M=3, term=2^3=8.
    • S={bit0}: condition that bit0 =1. Which numbers have bit0 set? 3,3 => two numbers? 2 has bit0=0. So M=2, term (-1)^1 * 2^2 = -4.
    • S={bit1}: numbers with bit1 set? 2 (10) has bit1 set, 3 (11) has bit1 set => all three? Actually 2 (binary 10) bit1=1, bit0=0; 3 (11) both. So all three have bit1=1? Check: a1=2 => bit1=1, a2=3 => bit1=1, a3=3 => bit1=1. So M=3, term = -2^3 = -8? sign negative because |S|=1 => (-1)^1 = -1, so term = -8.
    • S={bit0,bit1}: numbers with both bits set: only numbers with both 1: that's 3,3 => M=2, term positive (|S|=2) => +2^2=+4. Sum: 8 -4 -8 +4 =0. So answer 0. Good.

    So answer = Σ_{S ⊆ bits} (-1)^{|S|} 2^{M(S)}.

    Now M(S) = count of numbers that have all bits in S set. That is numbers i such that (a_i & mask(S)) == mask(S). So we need to compute for all subsets S of bits (size up to maybe 20, so at most 2^20 = 1,048,576 subsets) the count of numbers satisfying that condition. Since n can be up to 1e6, and bits up to 20, we can compute M(S) using SOS DP (Sum Over Subsets) technique. Actually we want for each mask (representing set of bits), the number of a_i such that (a_i & mask) == mask? That is count of numbers where mask is a subset of the bits set in a_i. More precisely, mask S corresponds to bits that must be 1. So we need count of numbers where (a_i bitwise includes S), i.e., (a_i & mask) == mask. This is standard: for each value v (0 <= v <= maxA ~ 10^6), we can count frequency f[v] = number of times v appears. Then we want for each mask, g[mask] = sum_{v: (v & mask) == mask} f[v]. This is like zeta transform over supersets. Because condition (v & mask) == mask means mask ⊆ bits(v) i.e., mask is a subset of the set of 1-bits of v. So g[mask] = sum_{v superset of mask in terms of bits} f[v]. That's a SOS DP: for each bit, we add from the set where that bit is off to the set where it's on. Standard SOS DP: we compute dp[mask] = sum over all sup of mask? Actually typical SOS DP for sum over subsets: dp[mask] = Σ_{sub ⊆ mask} f[sub]. But we need sum over supersets. There are two conventions: if we invert bits (consider complement), or compute over supersets directly. The standard method: initialize dp[mask] = f[mask] (frequency of exact value mask). Then for each bit i from 0 to maxbits-1, for mask from 0 to 2^maxbits-1, if mask has bit i = 0, then dp[mask] += dp[mask | (1<<i)]. That yields dp[mask] = sum over all supersets of mask (i.e., masks that have mask bits as 1). Because we propagate contributions from larger masks (with extra bits set) down to masks that are subsets. Indeed after running this, dp[mask] = Σ_{sup such that sup & mask == mask} f[sup]. That's exactly g[mask]. So we can compute that.

    Max bits: we need to cover up to max a_i (<= 10^6). 2^20 = 1,048,576, which is fine. So we can allocate array size 2^20 = 1<<20 = 1,048,576. That's about 4 MB for ints, or 8 MB for long long. Acceptable.

    We'll count frequency of each value. Since a_i up to 1e6, we can use array of size 2^20 (or maybe up to 2^20=1048576). Actually 1e6 < 2^20, so we can use size = 1<<20 = 1048576. However note that some values may be up to 10^6 which is less than 2^20, so covering all numbers up to 2^20 -1 is fine. So we'll use Nbits = 20? But what if a_i is exactly 1e6? 1,000,000 in binary is about 11110100001001000000? Actually 2^20 = 1,048,576 > 1e6, so 20 bits enough. But maybe there is a value 2^20 -1 = 1,048,575? It's less than 1e6? Actually 1,048,575 > 1e6, but input says ai ≤ 1e6, so max is 1,000,000. So 20 bits suffice, but note that the value 1,000,000 uses bits up to maybe 19? 2^19 = 524288, 2^20 = 1048576 > 1e6, so highest bit index 19 (0-indexed). So we can set B = 20 to be safe (covering bits 0..19). But wait 2^20 = 1,048,576 > 1e6, so we need mask up to 2^20 -1 = 1,048,575 which is > 1e6. However we only have frequencies for values up to 1e6. But SOS DP will consider all masks in range 0..(1<<B)-1. For masks that are > 1e6, there will be no contributions from f (since f=0 for those). That's fine.

    Thus we can compute dp[mask] = number of a_i such that (a_i & mask) == mask? Wait we want M(S) = count of numbers having all bits in S set. So for mask S, M(S) = dp[S] after SOS DP for supersets.

    Implementation steps:

    1. Read n.
    2. Determine maximum bit needed: find maxA, compute B = floor(log2(maxA)) + 1. But to be safe, we can just set B = 20 (since maxA <= 10^6 < 2^20). However, if maxA is exactly 0, B could be 1? But we can just use B=20 to keep consistent. That's fine because for bits above highest, they will be zero in all numbers, so M(S) for masks with bits beyond actual bits will be zero (since no number can have those bits set). But then our inclusion-exclusion sum over all subsets of bits: if we include bits that are never set, then M(S) for any S that includes such a bit will be 0. Then term 2^0=1 contributes. But is it valid to include all 20 bits? Let's consider: our inclusion-exclusion sum over all subsets of bits (including bits beyond the actual bits present in any number). In principle, the condition "all bits in S are set" for a bit that never appears as 1 in any number is impossible, so M(S)=0. Then our sum would include many terms. But does the formula still hold? The derivation originally considered bits up to some maximum; we can consider all possible bits in the universe (like up to 20). However, we must be careful: The condition for a subset to have AND zero is that for each bit j (even those beyond the highest present), it must have at least one element with 0 in that bit. But if a bit j never appears as 1 in any number, then automatically any subset satisfies "at least one element has 0" because all elements have 0. So the condition for those bits is always satisfied. Including them in inclusion-exclusion would produce additional terms, but does the formula still correctly account? Let's test: Suppose we have numbers only with bits 0..2, but we include bits 0..19. Then our sum Σ_{S⊆20 bits} (-1)^{|S|} 2^{M(S)} should still equal the desired number? Let's test with small: n=1, a=[0]. If we consider bits 0..19, M(∅)=1 => 2^1=2. For any non-empty S, M(S)=0 because no number has those bits set. So term = (-1)^{|S|} * 1. Sum over all non-empty subsets of 20 bits = Σ_{k=1}^{20} (-1)^k C(20,k) = -1 (since Σ_{k=0}^{20} (-1)^k C(20,k)=0 => sum_{k=1} = -C(20,0)= -1). So total = 2 + (-1) = 1. Still correct. So inclusion over all bits up to some fixed bound works as long as we include all bits that could possibly be 1? But if we include bits that are always zero, they add contributions that cancel out because the sum of signs over all subsets that include those bits yields something that effectively just multiplies the result by 1? Actually the formula holds for any set of bits considered, because the condition for those bits is always satisfied, and the inclusion-exclusion over those bits yields a factor 1. More formally, the formula answer = Σ_{S ⊆ Universe} (-1)^{|S|} 2^{M(S)} holds if M(S) counts numbers having all bits in S set; and if we include extra bits that are never set, M(S)=0 for any S that contains any such bit, so the terms factor as: total = Σ_{T ⊆ relevant bits} Σ_{U ⊆ irrelevant bits} (-1)^{|T|+|U|} 2^{M(T)} because M(T∪U) = M(T) if U contains only irrelevant bits? Actually if U contains any irrelevant bit (a bit never set), then condition "all bits in U set" cannot be satisfied by any number (since that bit is 0 for all numbers), so M(T∪U)=0. So for each fixed T (subset of relevant bits), contributions from all U (subsets of irrelevant bits) are: Σ_{U ⊆ Irr} (-1)^{|T|+|U|} * 2^{0} = (-1)^{|T|} 2^{M(T)} Σ_{U ⊆ Irr} (-1)^{|U|}. Σ_{U ⊆ Irr} (-1)^{|U|} = 0^{|Irr|}? Actually Σ_{U ⊆ Irr} (-1)^{|U|} = (1-1)^{|Irr|} = 0 if |Irr|>0, and 1 if Irr empty. So if there is at least one irrelevant bit, the sum over U of (-1)^{|U|} is 0, meaning contributions for any T would be multiplied by 0, giving total 0? But we got total 1 for the example. Wait check: In our example, with one number 0 and irrelevant bits set (say m_irr = 19). For T empty, M(∅)=1. Then contributions: for T=∅, sum over U ⊆ Irr of (-1)^{|U|} * 2^{M(∅)}? Actually M(T∪U) = M(U) because T empty, but M(U) = 0 if U non-empty, M(∅)=1. So careful: For U empty: term = (-1)^{0} * 2^{1} = 2. For U non-empty: term = (-1)^{|U|} * 2^{0} = (-1)^{|U|} * 1. So total for T=∅ = 2 + Σ_{U non-empty} (-1)^{|U|} = 2 + (Σ_{U ⊆ Irr} (-1)^{|U|} - 1) = 2 + (0 - 1) = 1. So the sum over U does not factor as product because M(T∪U) depends on whether U is empty or not; it's not simply 2^{M(T)} for all U. Since for non-empty U, M(T∪U)=0, not equal to M(T). So the contribution is not a simple factor. But the total sum still gives correct answer. So it's safe to consider all bits up to some bound, as long as we compute M(S) correctly (i.e., count numbers having all bits in S set). Then the sum over all subsets of those bits yields the correct answer. Since the SOS DP will compute M(S) correctly, we can simply take B = 20 (or maybe 20 is enough; but what if some number uses bit 20? max 1e6 < 2^20, so no. So B = 20 works. Alternatively, we could compute the max bit from input, set B = floor(log2(maxA)) + 1, but it's fine to fix B = 20.

    But we must ensure we cover all bits that could appear. Since maxA ≤ 10^6, 2^20 = 1,048,576 > 10^6, so 20 bits suffice. However, we need to consider that for SOS DP we need array size 2^B = 1<<20 = 1,048,576. That's okay.

    Now we compute dp[mask] = frequency of numbers equal to mask initially. But careful: a_i can be up to 1e6, which is less than 1<<20. So we can store freq in array of size 1<<20, but we may not need to store all values beyond maxA. But for simplicity allocate array of size 1<<20 and initialize zeros.

    Then we perform SOS DP for supersets: for i from 0 to B-1: for mask from 0 to (1<<B)-1: if ((mask >> i) & 1) == 0: dp[mask] += dp[mask | (1<<i)]. This yields dp[mask] = number of numbers that are supersets of mask (i.e., have all bits of mask set). That's M(mask). However, this includes the empty mask as well.

    Now we need to compute answer = Σ_{mask=0}^{2^B-1} (-1)^{popcount(mask)} * (2^{dp[mask]} mod MOD). Since dp[mask] could be up to n (1e6). We need to compute 2^{dp[mask]} mod MOD quickly. We can precompute pow2[0..n] array: pow2[i] = 2^i mod MOD. Since n up to 1e6, that's fine. Alternatively, compute on the fly using fast exponentiation but precomputation is efficient.

    Now the sum includes all masks from 0 to 2^B-1 (which is about 1e6). That is 1,048,576 masks, which is okay. For each mask we compute popcount and pow2[dp[mask]] and add or subtract.

    We also need to compute modulo properly. Since answer can be large, we compute mod 1e9+7.

    But careful: The answer formula includes all subsets of bits, including empty set. However, the answer we computed earlier gave sum_{S} (-1)^{|S|} 2^{M(S)}. Let's test with the sample where answer 10: n=4, a=[0,1,2,3]. Let's compute manually using our method. Values: 0 (00), 1 (01), 2 (10), 3 (11). Bits B=2? Actually max is 3, bits 0 and 1. So B=2. Masks from 0 to 3.

    Compute frequencies: f[0]=1, f[1]=1, f[2]=1, f[3]=1. Others 0.

    Perform SOS DP for supersets:

    Initialize dp[mask] = f[mask]. Iterate i=0: for mask, if bit0=0 (mask even): add dp[mask|1]. After i=0: mask0: dp[0] += dp[1] => 1+1=2 mask2: dp[2] += dp[3] => 1+1=2 mask1: bit0=1 skip mask3: skip. Now dp: [2,1,2,1]? Actually dp[0]=2, dp[1]=1, dp[2]=2, dp[3]=1.

    i=1 (bit1): For mask with bit1=0: masks where (mask & 2) == 0 -> mask 0 and 1. mask0: dp[0] += dp[2] => 2+2=4 mask1: dp[1] += dp[3] => 1+1=2 mask2: skip, mask3: skip. Result: dp[0]=4, dp[1]=2, dp[2]=2, dp[3]=1.

    Now M(mask) = dp[mask]. Indeed: mask 0: numbers superset of 0 -> all numbers => 4. mask 1 (bit0): numbers with bit0=1 => 1 and 3 => 2. mask 2 (bit1): numbers with bit1=1 => 2 and 3 => 2. mask 3 (both): numbers with both bits set => only 3 => 1.

    Now answer = Σ (-1)^{popcount(mask)} * 2^{M(mask)}: mask0: pop=0 => + 2^4 = 16 mask1: pop=1 => - 2^2 = -4 mask2: pop=1 => - 2^2 = -4 mask3: pop=2 => + 2^1 = +2 Total = 16 -4 -4 +2 = 10. Matches sample.

    Great.

    So algorithm steps:

    • Determine B = 20 (since maxA <= 10^6 < 2^20). Alternatively, compute maxA and set B = ceil(log2(maxA+1)) but 20 works.
    • size = 1 << B (i.e., 2^20 = 1048576).
    • freq array of size N = size, init zero.
    • For each a_i, increment freq[a_i].
    • dp = freq copy (maybe use same array).
    • For i in 0..B-1: for mask in 0..size-1: if ((mask >> i) & 1) == 0: dp[mask] += dp[mask | (1 << i)] (mod? but dp counts up to n=1e6, so we can store as int (32-bit) since max 1e6 fits. Use int, no mod needed for counts.)
    • Precompute pow2[0..n] mod MOD: pow2[0]=1; for i=1..n: pow2[i] = pow2[i-1]*2 % MOD.
    • ans = 0.
    • For mask in 0..size-1: cnt = dp[mask] (as int) term = pow2[cnt] (since dp[mask] <= n) if popcount(mask) % 2 == 0: ans = (ans + term) % MOD else: ans = (ans - term + MOD) % MOD
    • Output ans.

    Complexities: O(B * 2^B) = 20 * 1e6 = 20e6 ~ 20 million, which is fine. Memory: array of size 1<<20 ~ 1e6 ints ~ 4 MB, plus pow2 array of size n+1 ~ 1e6+1 ~ 4 MB, total < 10 MB, okay.

    But we must be careful: The SOS DP loops: for mask from 0 to size-1, but we need to ensure we update in place correctly. Standard approach: For each bit i, iterate mask from 0 to size-1, and if bit i is 0, add dp[mask | (1<<i)] to dp[mask]. This works because dp[mask | (1<<i)] may have been updated in the same i iteration? Actually the standard algorithm for superset sum uses the reverse order to avoid double counting? Let's think: In the typical SOS DP for subset sums, when doing dp[mask] = sum_{sub ⊆ mask} f[sub], we iterate bits and for mask from 0 to size-1, if mask has bit i set, then dp[mask] += dp[mask ^ (1<<i)]. That's safe because we are adding from smaller masks. For superset sums, we want dp[mask] = sum_{sup ⊇ mask} f[sup]. The standard method is: initialize dp[mask] = f[mask]. Then for i from 0 to B-1, for mask from 0 to size-1, if (mask & (1<<i)) == 0, then dp[mask] += dp[mask | (1<<i)]. This works because we are adding contributions from masks with the i-th bit set, which have been potentially updated with previous bits? Let's test with simple case: B=2, f[0]=1, f[1]=1, f[2]=1, f[3]=1. After initialization, dp = [1,1,1,1]. i=0: mask0 (00) has bit0=0 => dp[0] += dp[1] => becomes 2. mask1 (01) bit0=1 skip. mask2 (10) bit0=0 => dp[2] += dp[3] => becomes 2. mask3 (11) skip. Now dp = [2,1,2,1]. i=1: mask0 (00) bit1=0 => dp[0] += dp[2] => dp[2] is currently 2, so dp[0] becomes 4. mask1 (01) bit1=0? Actually mask1 (01) binary 01, bit1 corresponds to 2's place; (mask1 & 2) ==0, so yes bit1=0 => dp[1] += dp[3] => dp[3] =1, so dp[1] becomes 2. mask2 (10) bit1=1 skip. mask3 skip. Result dp = [4,2,2,1]. Works.

    If we iterate mask in reverse order? No, this order is fine because we are adding from masks that have the i-th bit set. In this forward order, dp[mask| (1<<i)] might have been updated earlier in this i iteration? For example, consider mask with bit i =0, and we add dp[mask| (1<<i)]. Since mask| (1<<i) has bit i set, it is not processed in the "if bit i ==0" branch, so it remains unchanged during this i iteration? Actually for a given i, we loop over all masks. For each mask, we only update dp[mask] if its bit i is 0. So masks with bit i=1 are never updated in this inner loop (they are not on the left side of assignment). So dp[mask | (1<<i)] is a mask with bit i=1, so it is not updated during this i iteration. However, dp[mask | (1<<i)] may have been updated earlier when we processed a different mask that had bit i=0 and added from it? But that's not possible because dp[mask | (1<<i)] is only updated if its own bit i is 0, which it isn't. So it remains unchanged during the i iteration. So the order doesn't matter, we can iterate from 0 to size-1. So it's safe.

    Thus we can implement as described.

    But we must also consider that a_i can be 0. That's fine.

    Now, potential pitfalls: pow2[dp[mask]] for dp[mask] = 0 gives 2^0 = 1. That's fine.

    Now, the sum over all masks of size 2^B. B=20 -> 1,048,576 masks. For each we compute popcount. We can compute popcount using builtin __builtin_popcount(mask) or precompute an array of size 2^B? 1e6 size array for popcount might be okay but not needed; we can compute on the fly; __builtin_popcount is fast.

    Now complexity wise, the SOS DP loop: for i in range(B): for mask in range(size): if condition -> add. That's 20*1e6 = 20M iterations, each with a simple conditional and addition. That's fine.

    But note: B=20 may be slightly higher than needed if maxA is smaller, but it's okay.

    Edge case: n=1e6, all a_i distinct? But frequency array of size 2^20 fits.

    Potential memory: using int for dp is fine. However, dp[mask] can be up to n=1e6, which fits in 32-bit.

    But we also need to compute pow2 up to n, which we can compute and store as int mod. Good.

    Now check sample 3: Input: 6 numbers: 5 2 0 5 2 1. Let's test quickly with our method mentally? Not necessary, but trust.

    Thus solution is clear.

    But wait: The problem statement: "sequence of indexes i1, i2, ..., ik (1 ≤ i1 < i2 < ... < ik ≤ n) a group of size k." So they consider any non-empty subsequence (i.e., subset). So counting subsets is correct.

    Now about modulo: We need answer modulo 1e9+7.

    Now we need to ensure that pow2 array: pow2[i] = 2^i mod MOD. For i up to n=1e6, compute easily.

    Now one more nuance: The inclusion-exclusion sum includes all subsets of bits, but we must confirm that we haven't miscounted groups where AND = 0, but also ensure that groups of size 0 (empty) are not counted. Our sum includes empty subset? Let's test: For n>0, empty group not counted because our formula gave non-empty only. Indeed we derived answer = Σ_{S} (-1)^{|S|} 2^{M(S)}. This includes contributions from M(∅)=n, term +2^n, and then subtracts etc. The result is number of non-empty subsets with AND zero. Example with n=0? Not applicable (n>=1). So we are fine.

    Thus solution is ready.

    Now we need to be careful about integer overflow in dp addition. Use int, but n up to 1e6, and dp[mask] can sum many frequencies, but maximum dp[0] = n (since all numbers are superset of mask 0). So it never exceeds n, safe.

    Now implement:

    C++ code:

    #include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; const int B = 20; const int SZ = 1 << B; // 2^20 = 1048576

    int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector freq(SZ, 0); int maxA = 0; for (int i=0; i<n; i++) { int a; cin >> a; freq[a]++; if (a > maxA) maxA = a; } // But we use fixed B = 20; no need to adjust based on maxA, but we can optionally compute B needed: while ((1<<B) <= maxA) B++? But we set fixed. // However if maxA is up to 1e6, B=20 is sufficient. If maxA is smaller, we still use size = 1<<20, but freq array size includes masks beyond maxA; that's okay. // SOS DP vector dp = freq; // copy for (int i=0; i<B; i++) { for (int mask=0; mask<SZ; mask++) { if (!(mask & (1<<i))) { dp[mask] += dp[mask | (1<<i)]; // no mod needed } } } // precompute powers of 2 vector pow2(n+1); pow2[0] = 1; for (int i=1; i<=n; i++) { pow2[i] = (pow2[i-1] * 2) % MOD; } long long ans = 0; for (int mask=0; mask<SZ; mask++) { int cnt = dp[mask]; int term = pow2[cnt]; if (__builtin_popcount(mask) % 2 == 0) { ans = (ans + term) % MOD; } else { ans = (ans - term + MOD) % MOD; } } cout << ans << endl; return 0; }

    Check: dp array is int and may hold up to n. pow2 array index up to n, cnt <= n, so ok.

    Potential improvements: Since SZ = 1<<20, but maybe maxA can be exactly 2^20 - 1? Actually max 1e6 < 2^20, but we still allocate 2^20. That's fine.

    But let's test with a case where B is less than needed? Could there be any a_i that uses bit 20? Since 2^20 = 1,048,576 > 1e6, but if a_i can be 1,000,000, that's less than 2^20. So all numbers are within [0, 2^20 - 1]. So B=20 works.

    Now, what about n=1e6, and we have 2^20 = 1,048,576, which is close to n. The SOS DP loops over 1,048,576 masks and 20 bits => ~21 million operations, each with a branch and addition. Should be fine.

    Now check correctness with sample 3.

    Let's compute manually quickly to ensure we haven't misinterpreted:

    Sample 3: n=6 a = [5,2,0,5,2,1] Write numbers in binary up to maybe bits 0-2? 5=101, 2=010, 0=000, 1=001. So bits 0,1,2 (0-indexed: bit0=1s, bit1=2, bit2=4). Max value 5 uses bits 0 and 2. So B=3? Actually 5 uses bits up to 2 (2^2=4). So B=3 gives size=8, which is enough. So we can test using B=3.

    Compute frequencies: values: 0->1,1->1,2->2 (since 2 appears twice),3->0,4->0,5->2 (since 5 appears twice),6->0,7->0. So f: [1,1,2,0,0,2,0,0].

    SOS DP:

    Initialize dp = f.

    i=0 (bit0): masks with bit0=0: even masks:0,2,4,6. mask0: dp[0] += dp[1] =>1+1=2 mask2: dp[2] += dp[3] =>2+0=2 mask4: dp[4] += dp[5] =>0+2=2 mask6: dp[6] += dp[7] =>0+0=0 others unchanged: dp[1]=1,dp[3]=0,dp[5]=2,dp[7]=0. Now dp: [2,1,2,0,2,2,0,0]

    i=1 (bit1): masks with bit1=0: those where (mask & 2)==0: masks 0,1,4,5. mask0: dp[0] += dp[2] =>2+2=4 mask1: dp[1] += dp[3] =>1+0=1 mask4: dp[4] += dp[6] =>2+0=2 mask5: dp[5] += dp[7] =>2+0=2 Others: dp[2]=2, dp[3]=0, dp[6]=0, dp[7]=0. Now dp: [4,1,2,0,2,2,0,0]

    i=2 (bit2): masks with bit2=0: those where (mask & 4)==0: masks 0,1,2,3. mask0: dp[0] += dp[4] =>4+2=6 mask1: dp[1] += dp[5] =>1+2=3 mask2: dp[2] += dp[6] =>2+0=2 mask3: dp[3] += dp[7] =>0+0=0 Others unchanged: dp[4]=2,dp[5]=2,dp[6]=0,dp[7]=0. Final dp: [6,3,2,0,2,2,0,0].

    Interpret M(mask): mask0:6 (all numbers) mask1 (001): numbers with bit0=1? Actually mask1 (bit0) => numbers with bit0=1: 5,5,1? Wait 1=001 has bit0=1, 5=101 has bit0=1, also? 2=010 bit0=0,0=000 bit0=0. So count: 1 (value1) + two 5's = 3. Yes dp[1]=3. mask2 (010): numbers with bit1=1? 2=010, 2=010 -> two, also maybe? 5=101 bit1=0, 1=001 bit1=0, 0 bit1=0. So 2. dp[2]=2. mask3 (011): numbers with bits0 and1 set: that would be 3 (011) but none present, so 0. dp[3]=0. mask4 (100): numbers with bit2=1: 5=101,5=101 => 2. dp[4]=2. mask5 (101): numbers with bits0 and2 set: 5,5 => 2. dp[5]=2. mask6 (110): bits1 and2: would be 6 (110) none ->0. mask7 (111): all bits: none ->0.

    Now compute answer: sum_{mask=0..7} (-1)^{popcount} * 2^{dp[mask]}: mask0 (pop0): + 2^6 = 64 mask1 (pop1): - 2^3 = -8 mask2 (pop1): - 2^2 = -4 mask3 (pop2): + 2^0 = +1 mask4 (pop1): - 2^2 = -4 mask5 (pop2): + 2^2 = +4 mask6 (pop2): + 2^0 = +1? Wait dp[6]=0 -> 2^0=1, popcount mask6=2 (bits1 and2) => even -> +1? Actually mask6 has bits 1 and 2 set: that's 2 bits -> even -> sign +. So +1. mask7 (pop3): - 2^0 = -1? mask7 bits 3, popcount=3 odd -> -1. Now sum: 64 -8 -4 +1 -4 +4 +1 -1 = 53. Indeed matches sample 53.

    Great.

    Thus solution correct.

    Potential pitfalls: For n up to 1e6, the SOS DP size 2^20 is about 1 million. But what if some numbers are larger than 2^20? But constraints say ai ≤ 10^6, so it's safe. However, to be robust, we might compute B = floor(log2(maxA)) + 1. But we need to ensure that B is at most 20. We can also use B = 20 to simplify.

    But there is a nuance: If maxA is, say, 0, then B = 1? But using B=20 is okay; dp array will have many masks with zero counts, but the inclusion-exclusion sum should still work? Let's test n=2, both numbers 0. maxA=0, B=20. Then freq[0]=2, others 0. SOS DP: after processing, dp[mask] = number of numbers that are supersets of mask. Since only number 0, which has no bits set, for any mask non-zero, superset condition requires all bits of mask set, but 0 has no bits set, so only mask=0 has supersets count 2; for any non-zero mask, dp[mask] = 0 (since no number has those bits). Now answer = Σ_{mask∈[0,2^20-1]} (-1)^{popcount} 2^{dp[mask]}. For mask=0: term = +2^2=4. For all other masks: dp[mask]=0 => term = (-1)^{popcount} * 1. So we need to compute sum_{mask≠0} (-1)^{popcount} = ? For the whole set of 2^20 masks, sum_{all masks} (-1)^{popcount} = (1-1)^{20}=0. So sum_{mask≠0} = - (term for mask0) because total sum = term0 + sum_{others} = 0 => sum_{others} = - term0 = -1? Actually term0 = (+1)*2^2? Wait careful: total sum over all masks: Σ_{mask} (-1)^{pop(mask)} * 2^{dp(mask)}. But dp(mask) is not constant for all non-zero masks? Actually for all non-zero masks, dp(mask)=0, so term = (-1)^{pop} * 1. So sum_{mask≠0} (-1)^{pop} * 1. And sum_{all masks} (-1)^{pop} = 0. So sum_{mask≠0} (-1)^{pop} = - (term for mask0? No, term for mask0 if we consider 2^{dp(0)}? Wait we must compute exactly: For mask=0, the term is (+1) * 2^{dp(0)} = 2^2=4. For non-zero masks, term = (-1)^{pop} * 1. So total sum = 4 + Σ_{mask≠0} (-1)^{pop}. And we know Σ_{mask≠0} (-1)^{pop} = -1 (since Σ_{all} = 0 => Σ_{non-zero} = - (term for mask0's sign? Actually for the sum of (-1)^{pop} over all masks, that's (1-1)^20 = 0, so Σ_{all} (-1)^{pop} = 0. But here Σ_{non-zero} we are summing (-1)^{pop} without factor. That's exactly Σ_{all} (-1)^{pop} - (+1 for mask0) = 0 - 1 = -1. So sum_{non-zero} (-1)^{pop} = -1. So total sum = 4 + (-1) = 3. Expected answer: For two zeros, subsets with AND zero: any non-empty subset: there are 3 subsets: single first, single second, both. AND of both zeros is 0. So answer 3. Good. So B=20 works even when maxA is zero.

    Thus fixed B=20 is fine.

    Now, what if n=10^6, and we allocate array of size 2^20 = 1,048,576, which is okay. But we also need to store pow2 array of size n+1 = 1e6+1, that's okay. Memory usage ~ (freq+dp) maybe 2 arrays of size 2^20 ints = 8 MB, pow2 array 4 MB, plus overhead ~12-16 MB, acceptable.

    We could reuse freq array as dp to save memory, but fine.

    Now, about the SOS DP loop: For each i, we need to iterate over all masks. Since SZ is 1,048,576, we have two nested loops. In C++, that's fine.

    Now, we should also consider the possibility of integer overflow in dp[mask] when adding. Since dp values are <= n <= 1e6, adding two such values gives <=2e6, which still fits in int (since int typical 32-bit can hold over 2e9). So safe.

    Now, careful: The dp array holds counts, not modulo. So no modulo.

    Now, edge case: n can be as high as 1e6, so pow2 array size n+1 = 1000001, we compute.

    Now, we need to ensure that we compute pow2 up to n, but dp[mask] can be up to n, so we need pow2[n] as max. So precomputing from 0 to n inclusive.

    Now, maybe we can also compute answer using Möbius inversion on the lattice of bit masks. That's exactly what we did.

    Thus solution is complete.

    But we must consider one more thing: The SOS DP we described computes for each mask the number of numbers that are supersets. That's M(mask). However, note that M(mask) counts the number of indices with (a_i & mask) == mask. That's correct.

    Now, test another random case manually: n=1, a=[7] (111). Then answer should be 0 because AND=7≠0. Compute with B=3. f[7]=1. SOS: dp[0]=1, dp[1]=? We'll compute quickly: after SOS, dp[mask] = 1 if mask is subset of 7, else 0. So dp[0]=1, dp[1]=1, dp[2]=1, dp[3]=1? Actually mask=3 (011) is subset of 7, so dp[3]=1. In fact, all masks that are subsets of 7 will have dp=1, others 0. Then answer = sum (-1)^{pop} 2^{dp}: mask0: +2=2 mask1: -2= -2? Actually 2^1=2, sign - => -2 mask2: -2 mask3: +2? pop2 even -> +2 mask4: -2? mask4 (100) pop1 -> -2 mask5: (101) pop2 -> +2 mask6: (110) pop2 -> +2 mask7: (111) pop3 -> -2 Sum: 2 -2 -2 +2 -2 +2 +2 -2 = 0. Good.

    Now test n=2, a=[0,7]. Expected answer: subsets: {0} => AND=0; {7}=>7 not; {0,7}=>0&7=0 => both? Actually 0&7 = 0, so subset {0,7} also yields 0. So answer 2. Our formula: frequencies: f[0]=1, f[7]=1. SOS: dp[mask] = number of numbers that are supersets of mask. For mask=0: both =>2. For mask non-zero: supersets are numbers that have all bits of mask set. For mask=1: both 0? Actually 0 does not have bit0 set, so only 7 qualifies =>1. mask=2: only 7 =>1. mask=4: only 7 =>1. mask=3: only 7 =>1? Since 7 has bits0,1,2 set, yes. mask=5: 7 qualifies. mask=6: 7 qualifies. mask=7: 7 qualifies =>1. For masks that are not subsets of 7, dp=0. So compute answer: sum_{mask} (-1)^{pop} 2^{dp}. We'll compute: mask0: +2^2=4 mask1: -2^1= -2 mask2: -2^1= -2 mask3: +2^1= +2 (pop2 even) mask4: -2^1= -2 mask5: +2^1= +2 (pop2) mask6: +2^1= +2 (pop2) mask7: -2^1= -2 (pop3) Now sum: 4 -2 -2 +2 -2 +2 +2 -2 = 2. Good.

    Thus correct.

    Now, regarding mod: In answer calculation, we are adding/subtracting terms mod MOD. term = pow2[cnt] is already mod MOD. So we can maintain ans as (ans +/- term + MOD) % MOD.

    Now, potential performance issues: The SOS DP inner loop over all masks for each bit can be optimized by iterating only over masks that have bit i = 0, and using a step pattern. But we can simply use full loop with conditional; 20 * 1e6 = 20 million, which is fine. Conditional might cause branch mispredictions but still okay for 1e6*20. In C++, often people write:

    for (int i=0; i<B; ++i) { for (int mask=0; mask<SZ; ++mask) { if ((mask & (1<<i)) == 0) { dp[mask] += dp[mask | (1<<i)]; } } }

    This is typical. Could also do reverse loops for subsets, but not needed.

    Now, one more nuance: The SOS DP we described computes dp[mask] = sum over all supersets of mask. But careful: In our inclusion-exclusion formula we need M(S) = number of indices i such that (a_i & S) == S. That's exactly dp[S] after superset DP. So it's correct.

    Now, about the mod: We need answer modulo 1e9+7. The terms 2^{M(S)} could be huge, but we compute modulo. However, note that our derivation didn't involve any modular arithmetic before, but we are taking modulo at the end. Since the sum is integer, modulo of sum is sum modulo. So it's fine.

    Now, check for potential overflow in ans accumulation: We use ans = (ans + term) % MOD etc, using long long for ans to avoid overflow before mod. Or we can use int and adjust.

    Now, check for n up to 10^6: pow2[1e6] computed by repeated multiplication mod MOD.

    Now, are there any pitfalls regarding the sign? We are using popcount parity.

    Now, we should also consider whether we need to consider that subsets of indices are considered ordered? No, it's just sets (groups). So counting subsets is correct.

    Now, can we have any other approach? The described approach is optimal.

    Now, ensure that we include only masks up to 2^B -1. Since B=20, that's 1,048,575. That covers all possible masks where bits are from 0..19.

    But what if some numbers have bits beyond 19? They don't. So fine.

    Now, I think the solution is ready.

    But wait: The constraint says ai ≤ 10^6, but 10^6 is exactly 1,000,000. 2^20 = 1,048,576 > 10^6. So we have numbers that are less than 2^20, but some numbers may be up to 10^6, which in binary may have bit 19 set? 2^19 = 524,288, 2^20 = 1,048,576. So 10^6 lies between, so bit 19 is set (since 2^19=524288, subtract from 10^6 remainder 475712, then bit 18? 2^18=262144, remainder 213568; bit 17=131072, remainder 82496; bit 16=65536, remainder 16960; bit 14=16384, etc). So bit 19 is set. So B must be at least 20. So using 20 is safe.

    Now, we also need to consider whether using B=20 and size = 1<<20 = 1048576, that's greater than max ai (10^6). But frequencies for indices beyond 10^6 are zero. So SOS DP still works.

    Now, about memory: we need dp array of size 1<<20, which is 1,048,576. Each int 4 bytes = ~4 MB. freq array also 4 MB. But we can avoid having two arrays by using freq as dp and updating in place: we can use vector dp = freq, and we can then reuse? Actually we need to read frequencies first, then do SOS on dp. But we could just use one array, fill with frequencies, then do SOS in place. So we can have a single vector dp(SZ). Read and increment dp[a] directly. Then run SOS on dp. That's what we can do: we don't need separate freq. So we can allocate just dp of size SZ. That saves memory (one array). But we also need pow2 array of size n+1. So total memory ~4 MB + 4 MB = 8 MB. That's fine. But we can also compute pow2 on the fly using fast exponentiation? But then for each mask we compute pow2, which would be expensive. Precomputation is better.

    Now, one more nuance: In the SOS DP, we are adding dp[mask | (1<<i)] to dp[mask]. Since dp[mask | (1<<i)] may have been updated in the same i iteration? As argued, it won't because for that mask, bit i is 1, so condition fails, so we never update dp[mask | (1<<i)] during this i iteration. However, what about the case where we are updating dp[mask] and then later in the same i iteration we might encounter a mask' where mask' | (1<<i) equals the mask we just updated? For mask' with bit i =0, we add dp[mask' | (1<<i)] which is a mask with bit i=1. That mask with bit i=1 is never updated in this i iteration, so its value is unchanged from the previous iteration or initial. However, we just updated dp[mask] (with bit i=0) earlier, but that doesn't affect dp[mask' | (1<<i)] because they are different masks. So safe.

    Thus implementation is straightforward.

    Now, we need to ensure we use fast I/O because n can be 1e6. So use ios::sync_with_stdio(false); cin.tie(nullptr);.

    Now, code.

    But one more possible optimization: If we compute B based on maxA, we could reduce the number of masks to 2^B where B is smaller when maxA is small, but not necessary.

    Now, confirm sample 2 and 3 outputs.

    Now, test more edge: n=1, a=[0] => answer=1. Our code: freq[0]=1, SOS yields dp[0]=1, for non-zero dp=0. Then answer = sum_{mask} (-1)^{pop} 2^{dp}. For mask0: +2^1=2. For others: sum_{mask≠0} (-1)^{pop}*1. As earlier, sum_{mask≠0} (-1)^{pop} = -1. So total = 1. Good.

    Now, if n=1, a=[x] where x>0, answer=0. Let's test with B=3 and x=5: we already did similar, sum=0.

    Now, what about n=2, a=[0,0] => answer=3. Already tested.

    Now, what about n=3, a=[0,0,0] => answer=2^3 -1 =7. Compute via formula: dp[0]=3, others 0. Answer = 2^3 + sum_{non-zero} (-1)^{pop}*1 = 8 + (-1) =7. Good.

    Now, large n with random numbers, should be fine.

    Now, let's think about alternative: Could we have used principle of counting subsets with AND=0 by using DP over bits via inclusion-exclusion of bits set? This is exactly that.

    Thus solution is final.

    Now, check the constraints: n up to 10^6, we allocate array of size 1<<20 = 1,048,576. This is fine. However, what about time: 20 million loops with addition and branch; that should be well under 1 second in optimized C++? Possibly around 0.1-0.2 seconds? Actually 20 million operations may be ~0.1-0.2 sec on modern CPUs if simple. But we also have reading 1e6 numbers and computing pow2 and final sum over 1M masks (1M popcount and additions). So total maybe 0.3-0.5 sec. Should be fine.

    Now, careful: The pow2 array size is n+1, but n could be up to 10^6. That's fine. We can compute as:

    pow2[0]=1; for (int i=1; i<=n; i++) pow2[i] = (pow2[i-1]*2) % MOD;

    Now, final answer: print ans.

    But one nuance: We used B=20. However, what if the numbers can have bits up to 20? We assumed 20 bits, but 2^20 = 1,048,576 > 10^6, but 10^6 < 2^20, so bit 19 is max, but what about bit 20? Actually bit index 20 corresponds to 2^20 = 1,048,576 which is >1e6, so no number can have that bit set. But we are including it in our universe, which is okay as we argued. However, we need to ensure that our SOS DP covers all bits up to B-1. If we set B=20, then we consider bits 0..19. That's fine. But what about bit 20? Not considered. But since no number can have that bit set, it's irrelevant. However, to be absolutely safe, we might set B=20 or B=21? Wait, 2^20 = 1,048,576, which is greater than 10^6. So numbers up to 1,000,000 have bits 0..19 only (since the highest possible value 2^20 -1 = 1,048,575, but we have max 1e6, so still within 0..19). So B=20 is sufficient.

    But to be precise: The number of bits needed to represent numbers up to 1e6 is floor(log2(1e6)) + 1 = 19 + 1? log2(1e6) ≈ 19.93, so 20 bits. So B=20.

    Thus we are okay.

    Now, final code.

    But double-check: In the SOS DP, we are adding dp[mask | (1<<i)] to dp[mask]. That operation may cause dp[mask] to exceed n? But as said, it's okay.

    Now, test sample 1 with B=20: we get answer 0, sample 2 10, sample 3 53.

    Now, consider potential integer overflow in the pow2 computation: we use modulo multiplication, safe.

    Now, we need to be careful about reading values: a_i can be up to 1e6, but we allocate array of size 1<<20 = 1048576, which is larger. So a_i fits as index.

    Now, implement.

    But wait: There's also a known trick: Since we only need counts for masks that appear or all masks up to maxMask = maybe (1<<B)-1, but using B=20 is fine.

    Now, possible improvement: Instead of doing inclusion-exclusion sum over all 2^B masks, we could use the SOS DP to compute the answer directly via Möbius transform, but we are already doing that.

    Now, check the modulo: For term = pow2[dp[mask]]; If dp[mask] is 0, term = 1. So we sum +/- 1 for many masks. But we need to ensure that the final answer is positive mod.

    Now, implementation details: Use __builtin_popcount(mask) to get parity. Or we can precompute parity for all masks up to SZ using a small table or iterative method, but __builtin_popcount is fast. However, for 1M masks, it's fine.

    Potential issue: __builtin_popcount returns number of set bits; we need parity. Could also use __builtin_parity, but that's also available. However, to avoid reliance on gcc extensions? In competitive programming, it's fine.

    Alternatively, we can compute parity with a loop or using precomputed array of 1<<16? But not needed.

    Now, also be careful about potential TLE due to popcount for 1M masks; popcount is hardware-accelerated on modern CPUs, should be very fast.

    Now, final code.

    But wait, there is an alternative approach that might be even more efficient: Use DP for counting subsets with AND exactly zero via principle of inclusion-exclusion over bits as we have done. This is standard.

    Now, consider if n is large (1e6) and we have B=20. Our SOS DP loops 20 * 1,048,576 = 20,971,520 ~ 21 million operations. That's fine.

    Now, we can also reduce the number of bits to the actual maximum bit present, but it's not necessary.

    Now, check memory: dp array of ints: 1,048,576 * 4 bytes = 4,194,304 bytes ~ 4 MB. pow2: (1e6+1)*4 = 4,000,004 ~ 4 MB. So total ~8 MB. That's acceptable.

    Now, code.

    But need to consider that the answer for sample 2 is 10, sample 3 is 53. Works.

    Now, we might also test with maximum random data to ensure performance. Should be okay.

    Now, final answer.

    Potential pitfalls: Did we correctly handle the case where a_i could be up to 10^6, but we are using B=20, which yields max mask 2^20-1 = 1,048,575. That's > 10^6, but there are indices from 1,000,001 to 1,048,575 that have frequency 0. So the dp array includes them. That's fine.

    Now, I'm thinking about whether the SOS DP for superset sum can be optimized by iterating masks in decreasing order? Not needed.

    Now, finalize.

    One more thing: In the inclusion-exclusion formula we have answer = Σ_{S⊆bits} (-1)^{|S|} 2^{M(S)}. This counts non-empty subsets with AND zero? Let's verify with empty set: For empty group (k=0) not counted. But does the sum include contribution from empty set that would correspond to counting empty group? Let's check: For S=∅, term = 2^{M(∅)} = 2^n. But then we subtract other terms, resulting in the number of non-empty subsets that satisfy condition. So empty subset is not included because 2^n includes all subsets (including empty) but then the other terms subtract the ones that don't satisfy condition? Actually 2^n counts all subsets (including empty) because 2^n = total number of subsets of n elements. But we then subtract some terms, and the result is exactly number of non-empty subsets with AND=0? Wait, we need to confirm: In our derivation we started with total non-empty subsets (2^n - 1). The final expression turned out to be Σ_{S} (-1)^{|S|} 2^{M(S)}. This sum includes empty S term 2^n. So the sum equals 2^n - Σ_{S≠∅} (-1)^{|S|+1} 2^{M(S)}. But earlier we had answer = 2^n - Σ_{S≠∅} (-1)^{|S|+1} 2^{M(S)}. And we confirmed with examples that it equals number of non-empty subsets with AND zero. So the sum Σ_{S} (-1)^{|S|} 2^{M(S)} indeed gives that number. So it's correct that it counts non-empty subsets only. Good.

    Now, consider possibility of overflow in the dp addition: we are adding counts that are <= n, but dp[mask] could become as large as n. In our SOS DP, dp[mask] accumulates from multiple supersets. For mask=0, dp[0] becomes n exactly because all numbers are superset of 0. For other masks, it's ≤ n. So safe.

    Now, check that we don't need to use long long for dp during SOS, as int suffices.

    Now, implement.

    But wait, there is a subtlety: In the SOS DP, we use dp[mask] as integer, but after we add dp[mask | (1<<i)], dp[mask] may become larger than n? No, it can't exceed n because it's counting the total number of numbers that are supersets of mask; that's at most n. So it's fine.

    Now, final code in C++.

    Testing quickly with sample:

    Input: 3 2 3 3 Our code: B=20, SZ=1<<20. freq[2]=1, freq[3]=2. SOS DP will compute correctly. Then answer should be 0.

    Now, one more test: n=0? Not allowed.

    Now, potential alternative: Use fast Walsh-Hadamard transform? But not needed.

    Now, we might want to optimize the final loop: For mask from 0 to SZ-1, we need to compute term = pow2[dp[mask]]; and add or subtract. Since dp[mask] is at most n, pow2 indexing is safe. However, pow2 array is of size n+1. But dp[mask] could be 0, which is fine.

    Now, ensure we have pow2 array sized n+1. n might be 1e6, so ok.

    Now, we can also compute 2^cnt via fast exponentiation each time to avoid storing pow2, but that would be slower (1M log operations). So precompute.

    Now, what about modulo subtraction: ans = (ans - term + MOD) % MOD; But better to do ans = (ans + MOD - term) % MOD; but both fine.

    Now, final code.

    But note: The problem states "Jzzhu have n non-negative integers a1, a2, ..., an." It says "groups" of indexes. So groups are subsets. So our answer correct.

    Now, we should also consider that the answer could be negative modulo, but we fix.

    Now, check for n=10^6, all a_i=0. Then dp[0]=n, all other masks dp=0. Then answer = 2^n - 1? Actually number of subsets with AND zero is all subsets, because AND of any subset of zeros is 0. So answer = 2^n - 1. Our formula: answer = Σ_{mask} (-1)^{pop} 2^{dp[mask]} = 2^n + Σ_{mask≠0} (-1)^{pop}*1 = 2^n + (-1) = 2^n - 1. Since n large, 2^n mod MOD computed via pow2[n] which we have. Good.

    Now, check for n large and random values, sum works.

    Thus solution is correct.

    Now, can we further reduce memory? We could combine dp and freq as said. Also we could compute pow2 on the fly using exponentiation by squaring for each distinct cnt, but not needed.

    Now, implement:

    #include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; const int B = 20; const int SZ = 1 << B;

    int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector dp(SZ, 0); for (int i = 0; i < n; i++) { int a; cin >> a; dp[a]++; } // SOS DP for superset sums for (int i = 0; i < B; i++) { for (int mask = 0; mask < SZ; mask++) { if ((mask & (1 << i)) == 0) { dp[mask] += dp[mask | (1 << i)]; } } } // precompute powers of two vector pow2(n + 1); pow2[0] = 1; for (int i = 1; i <= n; i++) { pow2[i] = (pow2[i - 1] * 2) % MOD; } long long ans = 0; for (int mask = 0; mask < SZ; mask++) { int cnt = dp[mask]; int term = pow2[cnt]; if (__builtin_popcount(mask) % 2 == 0) { ans += term; } else { ans -= term; } } ans %= MOD; if (ans < 0) ans += MOD; cout << ans << endl; return 0; }

    But we need to be careful: dp[mask] after SOS may be > n? No.

    Now, we used long long for ans to accumulate up to 1e6 terms of up to MOD (1e9), sum up to 1e15, fits in 64-bit. So ok.

    Now, final answer.

    Now, test with sample inputs:

    1. Input: 3 2 3 3 Our code: dp array after SOS? We'll trust.

    But we need to ensure that SZ is 1<<20, which is 1048576, and we are iterating over all masks, even those beyond the range of bits that could possibly matter. That's fine.

    Now, one more nuance: In the SOS DP, we used condition if ((mask & (1 << i)) == 0). But note that i goes from 0 to B-1 = 19. That's correct.

    Now, is there any risk of integer overflow in dp[mask] if we sum many counts? As argued, max is n.

    Now, we must ensure that we use the same type (int) for dp, but if we do dp[mask] += dp[mask | (1<<i)], it's safe.

    Now, to avoid any potential issues with large loops, we could add minor optimization: precompute parity of popcount for each mask using a small array of size maybe 1<<16 and combine, but not necessary.

    Now, final code as above.

    But wait, there's a catch: The SOS DP we implemented is for superset sums. However, the typical SOS DP for superset sums is usually done with the loop over masks in decreasing order? Let's double-check: I recall that for superset sums, one approach is: for i from 0 to B-1: for mask in 0..(1<<B)-1: if mask & (1<<i): dp[mask ^ (1<<i)] += dp[mask]. That's for subset sums? Actually there are two variants:

    • Subset sum: dp[mask] = sum_{sub ⊆ mask} f[sub]. After init, for i: for mask: if mask & (1<<i): dp[mask] += dp[mask ^ (1<<i)] (forward? Actually typical: for i: for mask in 0..(1<<B)-1: if mask & (1<<i): dp[mask] += dp[mask ^ (1<<i)]. This yields subset sums.

    • Superset sum: dp[mask] = sum_{sup ⊇ mask} f[sup]. After init, for i: for mask in 0..(1<<B)-1: if !(mask & (1<<i)): dp[mask] += dp[mask | (1<<i)]. This is what we used.

    Alternatively, we can also do: for i: for mask in (1<<B)-1 down to 0: if mask & (1<<i): dp[mask ^ (1<<i)] += dp[mask]. That would also give superset sums? Let's test: Suppose we start with f, then for each i, we iterate masks in decreasing order; if mask has bit i set, we add dp[mask] to dp[mask ^ (1<<i)]. This adds from larger mask to smaller mask (removing the i-th bit). After all bits, for any mask, dp[mask] will include contributions from all masks that are supersets of mask? Let's test with B=2, f[0]=1, f[1]=1, f[2]=1, f[3]=1. Initialize dp = f. i=0: iterate mask from 3 down to 0: mask=3: bit0 set -> dp[2] += dp[3] => dp[2]=1+1=2. mask=2: bit0 not set -> skip. mask=1: bit0 set -> dp[0] += dp[1] => dp[0]=1+1=2. mask=0: skip. Now dp = [2,1,2,1]. i=1: iterate mask from 3 down to 0: mask=3: bit1 set -> dp[1] += dp[3] => dp[1]=1+1=2. mask=2: bit1 set -> dp[0] += dp[2] => dp[0]=2+2=4. mask=1: bit1 not set -> skip. mask=0: skip. Result dp = [4,2,2,1]. Same as before. So both methods work. The method we used (forward over masks with condition on bit not set) is also correct. So fine.

    Now, check that we are not using the wrong order causing double counting. In our approach, for each i we iterate mask from 0 to SZ-1, and if (mask & (1<<i))==0, then dp[mask] += dp[mask | (1<<i)]. Let's simulate with a small case to see if there's any dependency on order that could cause using updated values incorrectly. In the forward order, consider mask=0 and mask=2 with bit i=0. For i=0, mask=0: we add dp[1] to dp[0]. Then later mask=2: we add dp[3] to dp[2]. Both dp[1] and dp[3] are masks with bit0=1, so they aren't updated during this i iteration. So no cross-effect. For i=1, mask=0: we add dp[2] to dp[0]; dp[2] was updated in previous i (i=0) but not in this i because mask=2 has bit1? Actually mask=2 (10) has bit1=1? Wait bit1 is the second bit; mask=2 binary 10, so bit1=1? For i=1, bit1 corresponds to 2. In our condition, we only update if (mask & (1<<i))==0. So for i=1, mask=2 has bit1=1, so we skip it. So dp[2] is not updated in this iteration. So when we add dp[2] to dp[0], we are using dp[2] as updated from previous i (i=0). That's correct because we want to incorporate contributions from numbers that have bit1 set? Actually the superset DP should after processing bit1 incorporate contributions from masks that have bit1 set to those that don't. So using dp[2] that already includes contributions from numbers that have bit1 set (since dp[2] counts numbers that have superset of mask 2, which after i=0 includes numbers that have bit0 set? But careful: After i=0, dp[2] = numbers that are supersets of mask 2? Let's check: After i=0, dp[2] originally had f[2] and we added dp[3] (which had f[3]). So dp[2] now includes numbers that have mask 2 as subset. That is numbers with bits1 set (since mask 2 corresponds to bit1 only). After i=0, it includes numbers that have bit1 set and also maybe bit0? Because dp[3] contributed numbers with both bits set. So dp[2] after i=0 correctly counts numbers that have bit1 set (regardless of bit0). Then during i=1, we add dp[2] to dp[0] (since dp[0] needs to include numbers that have bit1 set as superset). This is correct. So forward order works.

    Thus implementation is fine.

    Now, one more nuance: The value of B could be set to 20 as constant. But if maxA is larger than 2^20? Not possible.

    Thus solution is correct.

    Now, we must ensure we use appropriate data types. For pow2 array, we store int (modded). For dp, we store int.

    Now, let's think about potential TLE due to the SOS DP nested loops: 20 * 1,048,576 = 20,971,520. That's ~21e6. Each iteration does a check and maybe an addition. That's fine.

    But we might also consider that B can be reduced to the number of bits needed to represent the maximum a_i. We can compute maxA, then compute B = ceil(log2(maxA+1)). That could be up to 20 but could be less if maxA is small, saving time. But not necessary.

    But for safety, we could compute B as: int B = 0; while ((1 << B) <= maxA) B++; (or B = 20 if maxA==0? Actually if maxA=0, we could set B=1, but it's okay to use 20). Let's compute: if maxA=0, (1<<0)=1, 1>0? Actually while ((1<<B) <= maxA) B++ would not run because 1 <= 0 false, so B stays 0. That would be wrong because we need at least one bit to represent 0? But we need to consider bit0? If all numbers are zero, we still need to consider bit0? Actually if all numbers are zero, the condition for AND=0 is trivial, and our inclusion-exclusion sum over bits yields correct answer regardless of number of bits considered, as long as we consider at least one? Let's test: If we set B=0, then SZ=1<<0=1, only mask 0. Then answer = (-1)^0 * 2^{dp[0]} = 2^n. That would be total subsets (including empty). But we need to exclude empty subset, so answer would be 2^n instead of 2^n-1. So B must be at least 1 to include at least one bit for the inclusion-exclusion to subtract the empty subset effect. Wait our earlier derivation assumed there is at least one bit (the sum over all non-empty subsets of bits contributed -1). However, if there are zero bits (B=0), then the only mask is empty, and the sum yields 2^n. But we want 2^n - 1. So we need at least one bit to have the -1 contribution from non-empty subsets. But if all numbers are zero, there are no bits that ever appear as 1, but we still need to include at least one bit in our universe to get the -1 correction. In our fixed B=20, we have many bits, so the sum over non-empty masks yields -1, giving 2^n -1. So using B=20 works even when maxA=0. If we dynamically set B based on maxA, we might set B=0 (since maxA=0, maybe we think no bits needed), but that would give wrong answer. So we should not set B=0. So we could set B = max(1, ceil(log2(maxA+1))) or just fix B=20. So to be safe, we can compute B = 20. Or compute B = floor(log2(maxA)) + 1, but ensure B >= 1. But if maxA=0, then floor(log2(0)) undefined, so we need to treat separately. So easier: just set B=20. That ensures we have enough bits.

    But what about the case where maxA is less than 2^20, but we might have bits beyond the highest that are zero for all numbers; as we saw, this still works because the inclusion-exclusion over those bits results in a factor of (1-1)^{k}=0? Actually we need to include at least one bit? Wait earlier we considered the sum over all masks of (-1)^{pop} 2^{dp[mask]}. If we include extra bits that are always zero, then for any non-empty mask containing those bits, dp[mask]=0, term = (-1)^{pop}. So the sum over those extra bits contributes to the total. The total sum over all masks, including those extra bits, will still yield the correct answer (2^n - 1 for all zeros). So including many bits is fine.

    Thus we can fix B=20.

    Now, but consider the scenario where numbers use bits up to 19, and we set B=20, then the SOS DP will process 20 bits. That's fine.

    Now, confirm that the dp array after SOS for masks beyond the ones we care about (like mask >= 2^20? Actually SZ = 1<<20 = 1048576, masks 0..1048575. That's within range.

    Now, potential overflow in indexing: dp[a] where a up to 1e6, less than SZ. So fine.

    Now, finalize.

    But wait, what about the time for reading 1e6 integers? That's fine with fast I/O.

    Now, implement in code.

    One more improvement: We can compute parity using a precomputed array of size SZ if __builtin_popcount is slow? It's not.

    Now, test with maximum values: n=1e6, all a_i random up to 1e6. Our loops: SOS DP 21M iterations, final sum 1M iterations. Should run within time.

    Now, we should also note that the MOD is 1e9+7.

    Now, alternative method: Use DP for each bit, but we already have solution.

    Now, let's also think about the correctness of the inclusion-exclusion formula for the AND condition. Another way: Number of subsets with AND = 0 = Σ_{mask} (-1)^{popcount(mask)} 2^{freq_of_supersets_of_mask}. That's known.

    Now, confirm derivation: Using principle of inclusion-exclusion on bits, as we did.

    Now, we should also consider that the answer includes subsets of any size k>=1. Good.

    Now, we must ensure we output answer modulo 1e9+7.

    Now, I think it's done.

    But maybe there is a catch: The input size: n can be up to 10^6, but a_i can be up to 10^6. However, the SOS DP size 2^20 is about 1e6, but note that some a_i values may be > 2^20? No.

    Now, final code in answer.

    We'll present solution explanation with inclusion-exclusion and SOS DP.

    Now, I'll craft the final answer with explanation. We need to count the number of non-empty subsets of indices such that the bitwise AND of the chosen numbers is zero.
    Let the numbers have at most (M) bits; since (a_i \le 10^6 < 2^{20}) we can take (M = 20).

    For a subset of bits (S) (represented by a mask), define

    [ M(S) = #{,i \mid (a_i ,&, \text{mask}(S)) = \text{mask}(S),}, ]

    i.e., the number of array elements that have all bits of (S) set.

    Using inclusion–exclusion over the bits, the number of subsets whose AND is zero equals

    [ \sum_{S \subseteq {0,\dots,M-1}} (-1)^{|S|}; 2^{M(S)} . ]

    (Here the term for (S = \emptyset) gives (2^n); the alternating sum over non-empty (S) subtracts the unwanted subsets, leaving exactly the non‑empty groups with AND = 0.)

    Therefore we need to compute (M(S)) for every mask (S) (there are (2^M \approx 10^6) masks) and then evaluate the sum modulo (10^9+7).

    Computing (M(S))

    We start with a frequency array (\text{freq}[v]) for each value (v) ((0 \le v < 2^M)).
    (M(S)) is the number of values (v) such that (v) contains all bits of (S), i.e., (v) is a superset (in the bit sense) of (S).
    This is a classic sum over supersets problem and can be solved with SOS DP (Sum Over Subsets) in (O(M \cdot 2^M)).

    Algorithm:

    • Initialize (\text{dp}[mask] = \text{freq}[mask]).
    • For each bit (i = 0\ldots M-1):
      • For every mask from (0) to (2^M-1):
        • If the (i)-th bit of mask is 0, add (\text{dp}[mask \mid (1!\ll! i)]) to (\text{dp}[mask]).

    After processing all bits, (\text{dp}[mask] = M(mask)).

    Final answer

    Precompute powers of two modulo (10^9+7) up to (n): (\text{pow2}[k] = 2^k \bmod (10^9+7)).

    Then compute

    [ \text{ans} = \sum_{mask=0}^{2^M-1} (-1)^{\text{popcount}(mask)} \cdot \text{pow2}\big[\text{dp}[mask]\big] \pmod{10^9+7}. ]

    The total complexity is (O(M \cdot 2^M + n)), which with (M=20) and (n \le 10^6) runs well within limits.

    #include <bits/stdc++.h>
    using namespace std;
    
    const int MOD = 1000000007;
    const int B = 20;                 // 2^20 = 1 048 576 > 10^6
    const int SZ = 1 << B;
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    
        int n;
        cin >> n;
        vector<int> dp(SZ, 0);
        for (int i = 0; i < n; ++i) {
            int a;
            cin >> a;
            dp[a]++;                  // frequency of each exact value
        }
    
        // SOS DP for superset sums → M(S)
        for (int i = 0; i < B; ++i) {
            for (int mask = 0; mask < SZ; ++mask) {
                if ((mask & (1 << i)) == 0) {
                    dp[mask] += dp[mask | (1 << i)];
                }
            }
        }
    
        // powers of two modulo MOD
        vector<int> pow2(n + 1);
        pow2[0] = 1;
        for (int i = 1; i <= n; ++i) {
            pow2[i] = (pow2[i - 1] * 2) % MOD;
        }
    
        long long ans = 0;
        for (int mask = 0; mask < SZ; ++mask) {
            int cnt = dp[mask];
            int term = pow2[cnt];
            if (__builtin_popcount(mask) % 2 == 0) {
                ans += term;
            } else {
                ans -= term;
            }
        }
        ans %= MOD;
        if (ans < 0) ans += MOD;
        cout << ans << '\n';
    
        return 0;
    }