Cho ~N~ số nguyên không âm ~a_1, a_2, \ldots, a_N~ và một số nguyên dương ~M~. Hãy đếm số bộ ba chỉ số ~(i, j, k)~ với ~1 \le i, j, k \le N~ (các chỉ số có thể trùng nhau) mà ~a_i \cdot a_j \cdot a_k~ chia hết cho ~M~ (lưu ý nếu 2 bộ ba mà bộ này là hoán vị của bộ kia thì vẫn tính là 2 bộ, ví dụ ~(1, 2, 3)~ và ~(2, 1, 3)~ là 2 bộ khác nhau).

Dữ liệu

• Dòng đầu tiên là 2 số nguyên ~N~ và ~M~ ~(1 \le N \le 10^6,\ 1 \le M \le 3 \cdot 10^3)~.

• Dòng tiếp theo chứa ~N~ số nguyên không âm ~a_1, a_2, \ldots, a_N~ ~(0 \le a_i \le 10^9)~.

Kết quả

• In ra một dòng là số bộ ba số thoả mãn yêu cầu.

Ví dụ

Sample Input 1

2 5
1 5

Sample Output 1

7

Sample Input 2

10 3
1 2 3 4 5 6 7 8 9 10

Sample Output 2

657

Giải thích

Ở ví dụ thứ nhất có 7 bộ ba, giá trị tương ứng ~(a_i, a_j, a_k)~ là ~(1, 1, 5), (1, 5, 1), (1, 5, 5), (5, 1, 1), (5, 1, 5), (5, 5, 1), (5, 5, 5)~.

Chấm điểm

• Subtask 1 (20% số test): ~1 \le N \le 200~.

• Subtask 2 (20% số test): ~200 < N \le 2000~.

• Subtask 3 (20% số test): ~1 \le M \le 200~.

• Subtask 4 (40% số test): không có ràng buộc gì thêm.