Trong một phòng thí nghiệm có \(N\) mẫu vật, mỗi mẫu có mã gen \(A[i]\) (\(0 \le A[i] < 2^K\)). Các nhà khoa học muốn chọn bốn mẫu để tạo ra một tổ hợp đặc biệt, sao cho các gen chung của cả bốn (AND) đúng bằng một giá trị \(X\) cho trước.

Hãy đếm số bộ bốn \((i,j,k,l)\) phân biệt (\(i<j<k < l\)) thỏa mãn \(A[i] \& A[j] \& A[k] \& A[l] = X\).

Đầu vào:

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

Đầu ra:

• Số bộ bốn thỏa mãn AND đúng bằng \(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ộ bốn chỉ số \((i, j, k, l)\) (\(1 \le i < j < k < l \le N\)) sao cho \(a_i \text{ AND } a_j \text{ AND } a_k \text{ AND } a_l = 0\).

Ví dụ

Input:

5 3
1 2 4 6 7

Output:

5

Giải thích: Tất cả các bộ 4 số chọn từ mảng đều có AND bằng 0.

Ràng buộc & Subtasks