Nhân ngày 01/01/2021, Văn Quốc Khánh được mẹ cho một món quà, món quà được làm bằng hộp kim loại có mật khẩu. Mẹ Khánh rất thích những con số \(2^k\) với \(k\) là một số nguyên dương. Cho nên mật khẩu có dạng như sau:

Cho một số gồm \(N\) số nguyên dương \(A_1, A_2,\dots, A_N\), hãy chọn ra 3 số sao cho tích của 3 số đó chia hết cho \(2^k\). Hai cách chọn được xem là khác biệt khi có ít nhất một chỉ số ở cách 1 không có trong cách 2.

Ví dụ: \(1,2,3\) và \(2,1,4\) được xem là 2 cách khác biệt, còn \(2,1,3\) và \(3,2,1\) được xem là cùng 1 cách.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N,k\)
• Dòng thứ hai chứa dãy số \(A_1, A_2,\dots, A_N\)

Output

• Một số nguyên duy nhất là số lượng chọn được.

Scoring

• Subtask #1 (60% số testcase): \(N \leq 300, k \leq 20, A_i \leq 10^5\)
• Subtask #2 (40% số testcase): \(N \leq 2*10^5, k \leq 64, A_i \leq 10^{18}\)

Example

30 3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

1925