Trong một giải đấu game, mỗi người chơi có mã năng lực \(A[i]\) (\(0 \le A[i] < 2^K\)). Người ta muốn tìm những cặp game thủ có XOR mã năng lực đúng bằng một giá trị \(X\) cho trước, vì những cặp này sẽ tạo ra trận đấu cân bằng nhất.

Hãy đếm số cặp \((\)i < j\()\) thỏa mãn \(A[i] \oplus A[j] = 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ố cặp thỏa mãn XOR 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\)).
• Dòng 3: Số nguyên \(X\) (\(0 \le X < 2^K\)).

Định dạng đầu ra

• In ra số lượng cặp \((i, j)\) (\(1 \le i < j \le N\)) có \(a_i \oplus a_j = X\).

Ví dụ

Input:

4 3
1 2 3 4
3

Output:

1

Giải thích: Chỉ có cặp \((1, 2)\) có \(1 \oplus 2 = 3\).

Ràng buộc & Subtasks