Trong giải bóng rổ học đường, mỗi cầu thủ được gắn một mã chiến thuật \(A[i]\) (\(0 \le A[i] < 2^K\)). Một cặp chiến thuật được gọi là "đối lập" nếu chúng không có điểm chung nào, nghĩa là \(A[i] \& A[j] = 0\). Đây là cặp có thể phối hợp tốt nhất trên sân.

Hãy đếm số cặp cầu thủ có mã chiến thuật đối lập.

Đầu vào:

• Dòng 1: \(N, K\) (\(N \le 2 \cdot 10^5, K \le 20\))
• Dòng 2: \(N\) số nguyên \(A[1..N]\)

Đầu ra:

• Số cặp \((\)i < j\()\) mà \(A[i] \& A[j] = 0\).

#

Định dạng đầu vào

• Dòng 1: Hai số nguyên \(N\) và K (\(1 \le N \le 10^5, 1 \le K \le 20\)).
• Dòng 2: \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(0 \le a_i < 2^K\)).

Định dạng đầu ra

• In ra số lượng cặp \((i, j)\) (\(1 \le i < j \le N\)) sao cho \(a_i \text{ AND } a_j = 0\).

Ví dụ

Input:

4 3
1 2 4 6

Output:

4

Giải thích: Các cặp thỏa mãn là \((1, 2)\), \((1, 4)\), \((1, 6)\) (\(1 AND 6 = 0\)), \((2, 4)\). Tổng cộng 4 cặp.

Ràng buộc & Subtasks