Cho ~N~ số nguyên không âm ~a_1, a_2, ..., a_n~ và một số nguyên dương ~M~. Hãy đếm số bộ ba số ~(i,j,k)~ mà ~a_i ∗ a_j ∗ 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 ≤ N ≤ 10^6,1 ≤ M ≤ 3∗10^3)~.
• Dòng tiếp theo chứa ~N~ số nguyên không âm ~a_1, a_2, ... a_N (0 ≤ a_i ≤ 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 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 ≤ N ≤ 200~.
• Subtask 2 (20% số test): ~200 < N ≤ 2000~.
• Subtask 3 (20% số test): ~1 ≤ M ≤ 200~.
• Subtask 4 (40% số test): không có rằng buộc gì thêm.

Nguồn: Beginner Free Contest 29