시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB67462865.116%

문제

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 S1..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 S1..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 ≤ 106; 1 ≤ M ≤ 100 000) representing the given N and the size of the set of integers S1..M. The next line contains M integers Si (1 ≤ Si ≤ 106) representing the set of integers S1..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) ∉ S1..M.

예제 입력 1

10 4
4 6 7 10

예제 출력 1

6

This is the example from the problem description.

예제 입력 2

8 5
4 3 5 8 1

예제 출력 2

10

There are 10 pairs of <A, B> that satisfy the condition.

  • <1, 6> → (1 ⊕ 6) = 7
  • <2, 4> → (2 ⊕ 4) = 6
  • <2, 5> → (2 ⊕ 5) = 7
  • <3, 4> → (3 ⊕ 4) = 7
  • <3, 5> → (3 ⊕ 5) = 6
  • <4, 2> → (4 ⊕ 2) = 6
  • <4, 3> → (4 ⊕ 3) = 7
  • <5, 2> → (5 ⊕ 2) = 7
  • <5, 3> → (5 ⊕ 3) = 6
  • <6, 1> → (6 ⊕ 1) = 7

예제 입력 3

20 7
3 7 18 15 12 18 19

예제 출력 3

50

예제 입력 4

5 6
1 2 3 4 5 6

예제 출력 4

0