Nhân ngày \(01/01/2021\), hôm nay 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 dãy số gồm \(N\) số nguyên dương \(A_1,A_2,...,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.

• Yêu cầu : Hãy đếm xem có bao nhiêu cách chọn \(3\) số sao cho tích của \(3\) số đó chia hết cho \(2^k\).

Input

• Dòng đầu tiên gồm 2 số nguyên dương \(N\) và \(k\).
• Dòng thứ 2 là dãy số \(A_1,A_2,...,A_N\).

Output

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

• Sample Input :

  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

• Sample Output :

  1925

Ràng buộc

• Có 60% số điểm tương ứng với : \(N \le 300 , k \le 20 , A_i \le 10^5\).
• Có 40% số điểm tương ứng với : \(N \le 2.10^5 , k \le 64 , A_i \le 10^{18}\).

Nguồn: Nguyễn Đức Nhã (Algorit).