The Power of ALPS

Interview

Time limit1sMemory limit512 MB

Summary

Count pairs i<j with (Ai^2 + Ai*Aj + Aj^2) mod P equal to K, given N up to 1e5 and prime P up to 1e9.

Level: Medium7 of 10
Topics: Math, Number theory, Hash map, Combinatorics
Solved: No attempts yet

Problem

ALPS, the algorithm club of Gyeonggi Buk Science High School, was always pushed around and looked down on.

"C? Isn't that what the humanities kids learn? It's C the 'language', a language!"

"At a science high school you're messing around with computers instead of science... aren't you ashamed!"

But the ALPS members knew. A day would come when they could show everyone the power of computer science.

Then one winter, on the day of the first snow, a mysterious letter arrived at Gyeonggi Buk Science High School.

There is a sequence ${A_1, A_2, …, A_N}$ made of N distinct integers. A prime $P$ and an integer $K$ are also given. For an integer pair $(i, j)$ with $1 ≤ i < j ≤ N$ , call the pair a 'good pair' if the remainder of $A_i^2 + A_i \times A_j + A_j^2$ divided by $P$ is $K$ . For each of the cases written on the papers sent with the letter, find the number of good pairs.

If you find the correct value for every case, I will give you a prize of 45.6 billion won.

From,

Chaejun Lee, Class of 14

Next to the letter were papers densely filled with several test cases for the problem.

When the students of Gyeonggi Buk Science High School saw this letter, every one of them focused on solving the problem. But some of the values written on the papers were very large, and because of that, no matter how good at math the students were, solving the problem took too much time.

As everyone grew tired, the ALPS members felt their hearts stir. They knew this was the moment to show everyone the power of computers and good algorithms.

You have decided to solve this problem, feeling for this moment like an honorary ALPS member. To prove the power of computer science and the strength of ALPS to the students of Gyeonggi Buk Science High School, write a program that solves this problem correctly and quickly!

Input

The first line gives $N, P, K$ .

The second line gives the sequence $A_1, A_2, … , A_N$ .

Output

For the case given as input, print the number of good pairs.

Constraints

$2 ≤ N ≤ 10^5$
$2 ≤ P ≤ 10^9$
$0 ≤ K < P$
For every $1 ≤ i ≤ N$ , $0 ≤ A_i < P$ .
For every $1 ≤ i < j ≤ N$ , $A_i ≠ A_j$ holds.

Examples1

Example 1
Input
```
4 7 2
0 3 4 6
```
Expected output
```
3
```