알프스의 힘

경기북과학고의 알고리즘 동아리인 알프스(ALPS)는 늘 핍박과 멸시에 시달렸다.

“C언어? 그거 완전 문과 녀석들이나 배우는 거 아니야? C ‘언어’ 잖아 언어!”

“과학고에서 과학이 아니라 컴퓨터 같은거나 해대는군… 부끄럽지도 않은거냐고!”

하지만 알프스 부원들은 알고 있었다. 언젠가 컴퓨터 과학의 위력을 모두에게 보여줄 날이 온다는 것을.

그러던 어느 겨울, 첫눈이 내리던 날 의문의 편지 한 통이 경기북과학고에 도착했다.

서로 다른 N개의 정수로 이루어진 수열 ${A_1, A_2, …, A_N}$이 있습니다. 또한 소수 $P$와 정수 $K$가 주어집니다. 이때 $1 ≤ i < j ≤ N$인 정수쌍 $(i, j)$에 대해서 $A_i^2 + A_i \times A_j + A_j^2$을 $P$로 나눈 나머지가 $K$인 쌍을 ‘좋은 쌍’이라고 부릅시다. 편지와 함께 보낸 종이에 적힌 케이스들에 대해 좋은 쌍의 개수를 각각 구해주세요.

모든 케이스에 대해 올바른 값을 구하면 456억 원의 상금을 드리겠습니다.

From,

14기 이채준

편지 옆에는 문제에 해당하는 여러 테스트 케이스가 빼곡히 적힌 종이들이 함께 있었다.

이 편지를 본 경기북과학고 학생들은 너 나 할 것 없이 문제를 푸는 데 집중했다. 하지만 종이에 적힌 값 중에는 매우 큰 값도 있었고, 그 탓에 아무리 수학을 잘하는 학생이라도 문제를 푸는 데 너무 많은 시간이 걸렸다.

모두가 지쳐갈 무렵 알프스 부원들은 가슴의 울림을 느꼈다. 바로 이 순간이 컴퓨터와 좋은 알고리즘의 위력을 모두에게 보여줄 수 있는 순간이라는 것을 알았던 것이다.

당신은 지금 이 순간만은 명예 알프스 부원이라는 마음으로 이 문제를 해결하기로 결심하였다. 경기북과학고 학생들에게 컴퓨터 과학의 위력과 알프스의 힘을 증명하기 위해 이 문제를 정확하고 빠르게 풀어내는 프로그램을 작성하자!

첫 번째 줄에 $N, P, K$가 주어진다.

두 번째 줄에는 수열 $A_1, A_2, … , A_N$이 주어진다.

입력으로 주어진 케이스에 대해 좋은 쌍의 개수를 출력한다.

• $2 ≤ N ≤ 10^5$
• $2 ≤ P ≤ 10^9$
• $0 ≤ K < P$
• 모든 $1 ≤ i ≤ N$에 대해 $0 ≤ A_i < P$
• 모든 $1 ≤ i < j ≤ N$에 대해 $A_i ≠ A_j$를 만족한다.