26850번 - XOR Pairs 다국어

문제

XOR is a bitwise operator that evaluates the resulting bit into 1 if and only if their corresponding input bits differ (one of them is 1 while the other is 0). XOR operator is usually written with a symbol ⊕, or in most programming languages, the character ^(caret). For example, (10 ⊕ 6) = 12.

10 => 1010
 6 => 0110
 ----- ⊕
 1100 => 12

In this problem, you are given an integer N and a set of integers S_1..M. Your task is to count how many pairs of integers <A, B> such that 1 ≤ A, B ≤ (A ⊕ B) ≤ N, and (A ⊕ B) ∉ S.

For example, let N = 10 and S_1..4 = {4, 6, 7, 10}. There are 6 pairs of <A, B> that satisfy the condition.

• <1, 2> → (1 ⊕ 2) = 3
• <1, 4> → (1 ⊕ 4) = 5
• <1, 8> → (1 ⊕ 8) = 9
• <2, 1> → (2 ⊕ 1) = 3
• <4, 1> → (4 ⊕ 1) = 5
• <8, 1> → (8 ⊕ 1) = 9

Observe that a pair such as <2, 4> does not satisfy the condition for this example as (2 ⊕ 4) = 6 but 6 ∈ S. Another pair such as <5, 1> also does not satisfy the condition as it violates the requirement A, B ≤ (A ⊕ B).

입력

Input begins with a line containing two integers N M (1 ≤ N ≤ 10⁶; 1 ≤ M ≤ 100 000) representing the given N and the size of the set of integers S_1..M. The next line contains M integers S_i (1 ≤ S_i ≤ 10⁶) representing the set of integers S_1..M.

출력

Output contains an integer in a line representing the number of <A, B> such that 1 ≤ A, B ≤ (A ⊕ B) ≤ N and (A ⊕ B) ∉ S_1..M.

제한

힌트