You are given a prime number $p$, $n$ integers $a_1, a_2, \ldots, a_n$, and an integer $k$. 

Find the number of pairs of indexes $(i, j)$ ($1 \le i < j \le n$) for which $(a_i + a_j)(a_i^2 + a_j^2) \equiv k \bmod p$.


-----Input-----

The first line contains integers $n, p, k$ ($2 \le n \le 3 \cdot 10^5$, $2 \le p \le 10^9$, $0 \le k \le p-1$). $p$ is guaranteed to be prime.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le p-1$). It is guaranteed that all elements are different.


-----Output-----

Output a single integer — answer to the problem.


-----Examples-----
Input
3 3 0
0 1 2

Output
1
Input
6 7 2
1 2 3 4 5 6

Output
3


-----Note-----

In the first example:

$(0+1)(0^2 + 1^2) = 1 \equiv 1 \bmod 3$.

$(0+2)(0^2 + 2^2) = 8 \equiv 2 \bmod 3$.

$(1+2)(1^2 + 2^2) = 15 \equiv 0 \bmod 3$.

So only $1$ pair satisfies the condition.

In the second example, there are $3$ such pairs: $(1, 5)$, $(2, 3)$, $(4, 6)$.

Difficulty: competition

Starter code:

Solutions:
def check(num1, num2, p, k):
    v = num1 + num2
    v *= num1 * num1 + num2 * num2
    v %= p
    v += p
    v %= p
    return v == k % p

def __starting_point():

    n, p, k = (int(x) for x in input().split())
    idx___number = [int(x) for x in input().split()]

    idx___precount = [((pow(x, 4, p) - k * x) % p + p) % p for x in idx___number]

    met_precount___vals = {}
    ans = 0
    for number, precount in zip(idx___number[::-1], idx___precount[::-1]):
        if precount not in met_precount___vals:
            met_precount___vals[precount] = []
        else:
            for val in met_precount___vals[precount]:
                if check(number, val, p, k):
                    ans += 1
        met_precount___vals[precount].append(number)
    print(ans)

__starting_point()

from collections import Counter as C
N, P, K = list(map(int, input().split()))
A = [int(a) for a in input().split()]
X = C([(a**4-K*a)%P for a in A])
ans = 0
for x in X:
    ans += X[x]*(X[x]-1)//2
print(ans)


import sys
input = sys.stdin.readline

n,p,k=list(map(int,input().split()))
A=list(map(int,input().split()))

B=[(a**4-k*a)%p for a in A]

from collections import Counter
C=Counter(B)


print(sum([l*(l-1)//2 for l in list(C.values())]))


n,p,k=map(int,input().split())
d={}
ans=0
b=list(map(int,input().split()))
for i in range(n):
    a=b[i]
    val=(a**4-k*a)%p
    if d.get(val)==None:
        d[val]=1
    else:
        ans+=d[val]
        d[val]+=1
print(ans)

from collections import defaultdict
n,p,k = list(map(int,input().split()))
d = defaultdict(int)
a = list(map(int,input().split()))
ans = 0
for i in a:
    b = pow(i,4,p)
    temp = (i * k) % p
    fin = (b - temp) % p
    ans += d[fin]
    d[fin] += 1
print(ans)


l1 = input().split()
n = int(l1[0])
p = int(l1[1])
k = int(l1[2])
l = input().split()
A = {}

count = 0

e = []
for i in range(n):
    b = int(l[i])
    t = (b*b % p)*(b*b % p) - (k*b % p)
    t = t%p
    if t in A:
        A[t] += 1
    else:
        A[t] = 1

for x in A:
    count += int((A[x]*(A[x]-1))/2)
print(count)


from sys import stdin
n,p,k=list(map(int,stdin.readline().strip().split()))
s=list(map(int,stdin.readline().strip().split()))
st=set()
d=dict()
for i in s:
    x=(i**4-i*k)%p
    if x in st:
        d[x]+=1
    else:
        st.add(x)
        d[x]=1
s.sort()
ans=0
for i in s:
    x=(i**4-i*k)%p
    if x in st:
        ans+=(d[x]-1)*d[x]//2
        d[x]=0
print(ans)
    


from collections import Counter
def pr(a):return (a*(a-1))//2
n,p,k=list(map(int,input().split()))
a=list(map(int,input().split()))
a=Counter([(x**4-x*k+p)%p for x in a])
print(sum(pr(a[x]) for x in a))


from collections import Counter as C
N, P, K = list(map(int, input().split()))
A = [int(a) for a in input().split()]
X = C([(a**4-K*a)%P for a in A])
ans = 0
for x in X:
    ans += X[x]*(X[x]-1)//2
print(ans)



n,p,k=list(map(int,input().split()));
pairs = {}
count =0
for i in map(int,input().split()):
    t=(i**4-k*i)%p
    if t in pairs:
        count = count + pairs[t]
        pairs[t] += 1

    else:
        pairs[t] = 1

print(count)


from collections import Counter

n, p, k = map(int, input().split())
a = map(int, input().split())
ans = 0
for k, v in Counter([(x ** 4 - x * k) % p for x in a]).items() :
    ans += (v * (v - 1)) >> 1
print(ans)

n, p, k = map(int, input().split())

a = list(map(int, input().split()))

b = dict()

ans = 0
for i in a:
    j = (i ** 4 - k * i) % p
    c = b.get(j, 0)
    ans += c
    b[j] = c + 1
print(ans)

n, p, k = list(map(int, input().split()))
a = list(map(int, input().split()))
d = dict()
for i in range(n):
    now = a[i] * a[i] * a[i] * a[i] - k * a[i]
    now %= p
    if now in d:
        d[now] += 1
    else:
        d[now] = 1
ans = 0
for i in range(n):
    now = a[i] * a[i] * a[i] * a[i] - k * a[i]
    now %= p
    ans += d[now] - 1
ans //= 2
print(ans)


def expmod(a, n, m):
    if n == 0:
        return 1
    elif n == 1:
        return a%m
    res = n/2
    rem = n%2
    temp = expmod(a, res, m)
    if rem == 1:
        return temp*temp*a % m
    else:
        return temp*temp % m

n, p, k = list(map(int, input().split()))


a= list(map(int, input().split()))
holes = {}
res = 0
for i in range(0, n):
    temp = ((expmod(a[i], 4, p) - k*a[i])%p + p)%p
    if temp in holes:
        res+=holes[temp]
        holes[temp]+=1
    else:
        holes[temp]=1

print(int(res))


from collections import Counter
def pr(a):return (a*(a-1))//2
n,p,k=map(int,input().split())
a=map(int,input().split())
a=Counter([(x**4-x*k+p)%p for x in a])
print(sum(pr(a[x]) for x in a))

from collections import Counter
N, mod, K = map(int, input().split())
A = list(map(int, input().split()))
C = Counter()
for a in A:
    C[(a**4 - a*K)%mod] += 1

ans = 0

for v in C.values():
    ans += v*(v-1)//2

print(ans)

line = input()
line = line.split()
line = list([int(x) for x in line])
n = line[0]
p = line[1]
k = line[2]

inputs = input()
inputs = inputs.split()
inputs = list([int(x) for x in inputs])

dict = {}

counter = 0
for i in range(n):
    exped = (((inputs[i] ** 2) ** 2) - k * inputs[i]) % p

    if dict.get(exped, None) is None:
        dict[exped] = 0

    counter = counter + dict[exped]
    dict[exped] = dict[exped] + 1

print(counter)


from collections import defaultdict

n, p, k = map(int, input().split())
keys = list(map(int, input().split()))
dictionary = defaultdict(lambda: 0)
answer = 0

for key in keys:
    answer += dictionary[(key ** 4 - k * key) % p]
    dictionary[(key ** 4 - k * key) % p] += 1

print(answer)

from collections import defaultdict

n, p, k = map(int, input().split())
keys = list(map(int, input().split()))
dictionary = defaultdict(lambda: 0)
answer = 0

for key in keys:
    answer += dictionary[(pow(key, 4, p) - k * key) % p]
    dictionary[(key ** 4 - k * key) % p] += 1

print(answer)

from collections import defaultdict

n, p, k = map(int, input().split())
keys = list(map(int, input().split()))
dictionary = defaultdict(lambda: 0)
answer = 0

for key in keys:
    answer += dictionary[(pow(key, 4, p) - k * key) % p]
    dictionary[(key ** 4 - k * key) % p] += 1

print(answer)

import collections

n,p,k=map(int,input().split())
arr=list(map(int,input().split()))
dic=collections.defaultdict(int)
for i in range(n):
  tmp=arr[i]**4-arr[i]*k
  tmp%=p
  dic[tmp]+=1
ans=0
for key in dic.keys():
  ans+=(dic[key]*(dic[key]-1))//2
print(ans)

n, p, k = map(int, input().split())
a = list(map(int, input().split()))
d = {}
for x in a:
	v = (x**4 - k*x) % p
	if v < p:
		v += p
	if v not in d:
		d[v] = 1
	else:
		d[v] += 1
s = 0
for v in d.values():
	s += v * (v-1) // 2
print(s)