Trong quá trình nghiên cứu kiểm thử bằng đột biến (mutation testing), Lương nhận ra có những cặp số đặc biệt mà khi thay phép cộng thành phép nhân, đáp số vẫn không đổi. Lưu ý thêm rằng, phép tính trong máy tính đều được mod cho một số nào đó (thường là \(2^{32}\)). Vì thế Lương hỏi bạn bài toán sau:

Cho một dãy số tự nhiên \(a_1,a_2,\cdots,a_n\) và một số nguyên dương \(p\). Hãy tính số cặp \(i<j\) sao cho \(a_i+a_j\) và \(a_i∗a_j\) có cùng số dư khi chia cho \(p\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n,p (1 \leq n \leq 5∗10^5,2 \leq p \leq 10^9)\).
• Dòng thứ hai chứa \(n\) số tự nhiên \(a_1,a_2,\cdots,a_n (0 \leq a_i \leq 10^9)\).

Output

• In ra một dòng là đáp số cần tìm.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(p=10^9\) và \(0 \leq a_i \leq 10^4\)
• Subtask \(2\) (\(25\%\) số điểm): \(p \leq 2000\)
• Subtask \(3\) (\(25\%\) số điểm): p là số nguyên tố.
• Subtask \(4\) (\(25\%\) số điểm): không có điều kiện gì thêm.

Example

4 2
0 1 2 3 

1

3 3
2 5 3 

1