Trong một hệ thống mạng, mỗi máy tính được gán một mã bảo mật \(A[i]\) (\(0 \le A[i] < 2^K\)). Một nhóm ba máy được gọi là "liên minh" nếu hội tụ mã của chúng đúng bằng \(X\), tức là \(A[i] \mid A[j] \mid A[k] = X\).

Cho trước giá trị \(X\), hãy đếm số bộ ba \((i,j,k)\) phân biệt (không kể thứ tự) có mã hội tụ đúng bằng \(X\).

Đầu vào:

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

Đầu ra:

• Số bộ ba \((\)i<j < k\()\) mà \(A[i] \mid A[j] \mid A[k] = X\).

#

Đị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 bộ ba \((i, j, k)\) (\(1 \le i < j < k \le N\)) có \(a_i \text{ OR } a_j \text{ OR } a_k = 2^K - 1\).

Ví dụ

Input:

4 3
1 2 4 7

Output:

4

Giải thích: Bộ ba (1, 2, 4) có OR = 7, và các bộ ba chứa 7 đều có OR = 7.

Ràng buộc & Subtasks