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 ~(a_i, a_j, a_k)~ (các chỉ số ~i,j,k~ có thể trùng nhau) thỏa mãn ~a_i \times a_j \times 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.

Input

• Dòng đầu tiên là ~2~ số nguyên ~N~ và ~M~ ~(1 \le N \le 10^6,~ ~1 \le M \le 3.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)~.

Output

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

Samples

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

Clarification

Ở 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)~.

Scoring

• 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.