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\ast a_j\ast 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\ast {10}^3)$.
• Dòng tiếp theo chứa $N$ số nguyên không âm $a_1,a_2,...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 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.

Nguồn: Beginner Free Contest 29