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 (1 \le i, j, k \le n)~ 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.

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 số thoả mãn yêu cầu.

Sample

Input #1

2 5
1 5

Output #1

7

Input #2

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

Output #2

657

Hint

Giải thích #1: 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)~.