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: HARD
Tags: Mathematics

Matrices

Amortized analysis

Number theory
Skill types: Amortized analysis

Starter code:

Solutions:
import sys
import math

def read_line():
	return sys.stdin.readline()[:-1]

def read_int():
	return int(sys.stdin.readline())

def read_int_line():
	return [int(v) for v in sys.stdin.readline().split()]

def read_float_line():
	return [float(v) for v in sys.stdin.readline().split()]

def nc2(n):
	return n * (n - 1) // 2
(n, p, k) = read_int_line()
a = read_int_line()
ans = []
for i in range(n):
	ans.append((a[i] ** 4 - a[i] * k) % p)
d = {}
for i in ans:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
al = list(d.values())
ans = 0
for i in al:
	if i != 1:
		ans += nc2(i)
print(ans)


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

def f(a):
	return ((pow(a, 4, p) - k * a) % p + p) % p

def g(a):
	return a * (a - 1) // 2
res = 0
for a in arr:
	v = f(a)
	if v in cnt:
		cnt[v] += 1
	else:
		cnt[v] = 1
for a in arr:
	v = f(a)
	res += g(cnt[v])
	cnt[v] = 0
print(res)


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


cond = [int(x) for x in input().split()]
n = cond[0]
p = cond[1]
k = cond[2]
a = [int(x) for x in input().split()]
b = [(x ** 4 - k * x) % p for x in a]
d = {}
r = 0
for x in b:
	if x not in d:
		d[x] = 0
	r += d[x]
	d[x] += 1
print(r)


(n, p, k) = map(int, input().split())
a = list(map(int, input().split()))
a = [(i ** 4 - i * k) % p for i in a]
c = {i: 0 for i in a}
for i in a:
	c[i] += 1
s = 0
for i in c:
	i = c[i]
	s += i * (i - 1) // 2
print(s)


(n, p, k) = [int(i) for i in input().split()]
l = [int(i) for i in input().split()]
di = {}
ans = 0
for i in l:
	x = (i * i * i * i - k * i) % p
	if x in di:
		ans += di[x]
		di[x] += 1
	else:
		di[x] = 1
print(ans)


def Sum(n):
	return n * (n - 1) // 2

def Solver(p, k, a):
	aux = []
	for i in a:
		aux.append((i ** 4 - i * k) % p)
	dic = {}
	for i in aux:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
	val = list(dic.values())
	sol = 0
	for i in val:
		if i > 1:
			sol += Sum(i)
	return sol

def Main():
	(n, p, k) = map(int, input().split())
	a = list(map(int, input().split()))
	sol = Solver(p, k, a)
	print(sol)
Main()


(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)


(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)


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) = 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))


(n, p, k) = map(int, input().split())
arr = list(map(int, input().split()))
dct = {}
answer = 0
for elem in arr:
	val = (elem ** 4 - k * elem) % p
	if val in dct:
		answer += dct[val]
		dct[val] += 1
	else:
		dct[val] = 1
print(answer)


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


(n, p, k) = map(int, input().split())
a = [int(x) for x in input().split()]
m = {}
for i in a:
	t = (i * i * i * i - k * i) % p
	if t in m:
		m[t] += 1
	else:
		m[t] = 1
ans = 0
for key in m:
	if m[key] >= 2:
		ans += (m[key] - 1) * m[key] // 2
print(ans)


line = input()
line = line.split()
line = list(map(lambda x: int(x), line))
n = line[0]
p = line[1]
k = line[2]
inputs = input()
inputs = inputs.split()
inputs = list(map(lambda x: int(x), 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)


(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 Counter
(n, p, k) = map(int, input().split())
arr = [(x ** 4 - k * x) % p for x in list(map(int, input().split()))]
print(sum([x * (x - 1) // 2 for x in Counter(arr).values()]))


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


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)


(n, p, k) = 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)


(n, p, k) = [int(i) for i in input().split()]
data = [int(i) for i in input().split()]
dic = {}
for d in data:
	val = (pow(d, 4, p) - d * k) % p
	if val in dic:
		dic[val] += 1
	else:
		dic[val] = 1
ans = 0
for am in dic.values():
	ans += am * (am - 1) // 2
print(ans)


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)


from collections import defaultdict
(n, p, k) = 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)


import collections
(n, p, k) = map(int, input().split())
A = [int(i) for i in input().split()]
B = [0] * n
for i in range(n):
	B[i] = (pow(A[i], 4, p) - k * A[i]) % p
C = collections.Counter(B).values()
ans = 0
for c in C:
	if c > 1:
		ans += c * (c - 1) // 2
print(ans)


def solve(dic, elem):
	if elem in dic:
		dic[elem] += 1
	else:
		dic[elem] = 1
(n, p, k) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = {}
res = 0
for i in range(n):
	val = (a[i] ** 4 - k * a[i]) % p
	solve(b, val)
for key in b:
	t = b[key]
	res += t * (t - 1) // 2
print(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)))


(n, p, k) = input().split()
lst = [int(x) for x in input().split()]
p = int(p)
k = int(k)
from collections import defaultdict
counts = defaultdict(int)
for num in lst:
	counts[(num ** 4 - k * num) % p] += 1
total = 0
for key in counts:
	val = counts[key]
	total += val * (val - 1) // 2
print(total)


(n, p, k) = map(int, input().split())
a = list(map(int, input().split()))
a = list(((i ** 4 - k * i) % p for i in a))
cnt = set(a)
cnt = dict(zip(cnt, [0] * len(cnt)))
ans = 0
for i in a:
	ans += cnt[i]
	cnt[i] += 1
print(ans)


import sys
input = sys.stdin.readline
(n, p, k) = 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())
c = 0
cnt = {}
for i in map(int, input().split()):
	t = (i ** 4 - k * i) % p
	if t in cnt:
		c += cnt[t]
		cnt[t] += 1
	else:
		cnt[t] = 1
print(c)


from collections import defaultdict as dd
(n, p, k) = map(int, input().split())
a = [int(i) for i in input().split()]
d = dd(lambda : 0)
for i in a:
	d[(i ** 4 - k * i) % p] += 1
ans = 0
for i in d.values():
	ans += i * (i - 1) // 2
print(ans)


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)


(n, p, k) = map(int, input().split())
l = list(map(int, input().split()))
d = dict()
for y in range(n):
	x = pow(l[y], 4) - l[y] * k
	if x % p not in d:
		d[x % p] = 1
	else:
		d[x % p] += 1
ct = 0
for (k, v) in d.items():
	ct += v * (v - 1) // 2
print(ct)


from collections import defaultdict
(n, p, k) = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
d = defaultdict(int)
s = defaultdict(set)
for el in a:
	val = (el ** 4 - k * el) % p
	if el not in s[val]:
		s[val].add(el)
		ans += d[val]
		d[val] += 1
	else:
		ans += d[val] - 1
		if 4 * el ** 3 % p == k:
			ans += 1
print(ans)


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)


(n, p, k) = map(int, input().split())
arr = list(map(int, input().split()))
dict1 = {}
for i in range(n):
	val = (pow(arr[i], 4, p) - k * arr[i] % p + p) % p
	try:
		dict1[val] += 1
	except:
		KeyError
		dict1[val] = 1
ans = 0
for i in dict1.keys():
	ans += dict1[i] * (dict1[i] - 1) // 2
print(ans)


from collections import Counter
(n, p, k) = map(int, input().split())
c = Counter(((pow(v, 4, p) - k * v) % p for v in map(int, input().split())))
print(sum((v * (v - 1) // 2 for v in c.values())))


from collections import defaultdict
from collections import Counter
import sys
input = sys.stdin.readline
inf = 100000000000000000
(n, mod, k) = map(int, input().split())
A = list(map(int, input().split()))
D = Counter()
for a in A:
	num = a ** 4 - a * k
	while num < 0:
		num += mod
	num %= mod
	D[num] += 1
ans = 0
for d in D.values():
	ans += d * (d - 1) // 2
print(ans)


from collections import defaultdict
(n, p, k) = map(int, input().split())
cnt = defaultdict(lambda : 0)
for x in map(int, input().split()):
	cnt[x * (x ** 3 - k) % p] += 1
print(sum((x * (x - 1) // 2 for x in cnt.values())))


from sys import stdin, stdout
import collections
import math
(N, P, K) = [int(x) for x in stdin.readline().split()]
arr = [int(x) for x in stdin.readline().split()]
freq = {}
for num in arr:
	mod = 1
	for i in range(4):
		mod = mod * num
		mod = mod % P
	mod -= K * num
	mod = mod % P
	if mod not in freq:
		freq[mod] = 1
	else:
		freq[mod] += 1
res = 0
for key in freq:
	F = freq[key]
	res += F * (F - 1) // 2
print(res)


(n, p, k) = map(int, input().split())
A = list(map(int, input().split()))
step4 = {}
for i in A:
	h = i ** 4 - k * i
	h %= p
	if h not in step4:
		step4[h] = 0
	step4[h] += 1
ans = 0
for u in step4:
	ans += step4[u] * (step4[u] - 1) // 2
print(ans)


iarr = list(map(int, input().split()))
n = iarr[0]
p = iarr[1]
k = iarr[2]
arr = list(map(int, input().split()))
for i in range(n):
	arr[i] = (pow(arr[i], 4, p) - k % p * (arr[i] % p) % p) % p
dic = {}
for i in range(n):
	try:
		dic[arr[i]] += 1
	except:
		dic[arr[i]] = 1
ans = 0
for i in dic:
	ans += dic[i] * (dic[i] - 1) // 2
print(ans)


from collections import Counter
(n, p, k) = map(int, input().split())
a = [int(x) for x in input().split()]
b = [x ** 4 % p for x in a]
c = [x * k % p for x in a]
d = [(b[i] - c[i] + p) % p for i in range(n)]
f = Counter(d)
s = 0
for (_, e) in f.items():
	s += e * (e - 1) // 2
print(s)


from collections import defaultdict
(n, p, k) = list(map(int, input().split()))
l = list(map(int, input().split()))
count = 0
dic = defaultdict(int)
for i in range(n):
	value = (l[i] ** 4 % p - k * l[i] % p) % p
	count += dic[value]
	dic[value] = dic[value] + 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)


import sys
input = sys.stdin.readline
(n, p, k) = map(int, input().split())
a = list(map(int, input().split()))
MOD = p
memo = {}
for i in range(n):
	num = (a[i] ** 4 - a[i] * k) % MOD
	if num not in memo:
		memo[num] = 1
	else:
		memo[num] += 1
ans = 0
for i in memo:
	ans += memo[i] * (memo[i] - 1) // 2
print(ans)


(n, p, k) = map(int, input().split())
arr = list(map(int, input().split()))
d = {}
for i in arr:
	x = i * i % p * i % p * i % p
	y = i * k % p
	cc = (x - y + p) % p
	if cc in d:
		d[cc] += 1
	else:
		d[cc] = 1
ans = 0
for (key, value) in d.items():
	cc = value * (value - 1) // 2
	ans += cc
print(ans)


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


(n, p, k) = map(int, input().split())
a = list(map(int, input().split()))
h = []
for i in a:
	h.append((i * i * i * i - k * i) % p)
from collections import Counter
j = Counter(h)
su = 0
for i in j:
	su += j[i] * j[i] - j[i]
print(su // 2)


(n, q, k) = map(int, input().split())
a = [int(x) for x in input().split()]
mp = dict()
for i in range(n):
	mp[(a[i] ** 4 - k * a[i]) % q] = 0
for i in range(n):
	mp[(a[i] ** 4 - k * a[i]) % q] += 1
ans = 0
for key in mp:
	d = mp[key]
	ans += d * (d - 1) // 2
print(ans)


ln = [int(i) for i in input().split(' ')]
n = ln[0]
p = ln[1]
k = ln[2]
a = [int(i) for i in input().split(' ')]
cts = {}
ctsc = {}
ans = []
nm = 0
for i in range(0, len(a)):
	an = (a[i] ** 4 - k * a[i]) % p
	if an in ctsc:
		nm += ctsc[an]
		ctsc[an] += 1
	else:
		ctsc[an] = 1
print(nm)


(n, p, k) = [int(i) for i in input().split(' ')]
a = [int(i) for i in input().split(' ')]
b = []
for i in range(n):
	b.append((pow(a[i], 4, p) - k * a[i]) % p)
mydic = {}
for i in b:
	mydic[i] = 0
for i in b:
	mydic[i] += 1
ans = 0
for t in mydic:
	ans += mydic[t] * (mydic[t] - 1) // 2
print(ans)


(n, p, k) = list(map(int, input().strip().split()))
a = list(map(int, input().strip().split()))
d = dict()
for el in a:
	r = 1
	r *= el
	r %= p
	r *= el
	r %= p
	r *= el
	r %= p
	r *= el
	r %= p
	s = k * el % p
	r -= s
	r %= p
	try:
		d[r] += 1
	except:
		d[r] = 1
c = 0
for k in d.keys():
	c += d[k] * (d[k] - 1) // 2
print(c)


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)


from collections import defaultdict as dc
(n, p, k) = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(n):
	x = (a[i] ** 2 % p) ** 2 % p - k * a[i] % p
	if x < 0:
		b.append(x + p)
	else:
		b.append(x)
d = dc(int)
for i in b:
	d[i] += 1

def c(n):
	return n * (n - 1) // 2
cnt = 0
for i in list(d.values()):
	cnt += c(i)
print(cnt)


def main():
	(n, p, k) = map(int, input().split())
	ans = list(map(int, input().split()))
	for i in range(n):
		temp = ans[i]
		ans[i] = (temp ** 4 - temp * k) % p
	mp = {}
	for i in ans:
		mp.setdefault(i, 0)
		mp[i] = mp[i] + 1
	temp = 0
	for i in mp.values():
		temp = i * (i - 1) // 2 + temp
	print(temp)
main()


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)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 998244353

def solve():
	(N, P, K) = getInts()
	A = getInts()
	B = dd(int)
	for a in A:
		X = pow(a, 4, P) - K * a
		X %= P
		B[X] += 1
	ans = 0
	for (key, val) in B.items():
		ans += val * (val - 1) // 2
	return ans
print(solve())


def check(num1, num2, p, k):
	v = num1 + num2
	v *= num1 * num1 + num2 * num2
	v %= p
	v += p
	v %= p
	return v == k % p
(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)


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


(n, p, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
counter = 0
b = {}
for item in a:
	x = (item ** 4 - k * item) % p
	if x not in b:
		b[x] = 1
	else:
		b[x] += 1
for item in b:
	counter += b[item] * (b[item] - 1) // 2
print(counter)


def tianjia(dic, z):
	if z in dic:
		dic[z] += 1
	else:
		dic[z] = 1
(n, p, k) = map(int, input().split())
z = 0
l = list(map(int, input().split()))
dic = {}
for i in l:
	z = (i ** 4 - i * k) % p
	tianjia(dic, z)
print(sum([dic[i] * (dic[i] - 1) // 2 for i in dic]))


import sys
(n, p, k) = list(map(int, sys.stdin.readline().strip().split()))
a = list(map(int, sys.stdin.readline().strip().split()))
for i in range(0, n):
	a[i] = (a[i] ** 4 - k * a[i]) % p
	a[i] = a[i] + 2 * p
	a[i] = a[i] % p
a.sort()
c = 1
x = a[0]
ans = 0
for i in range(1, n):
	if a[i] == x:
		c = c + 1
	else:
		ans = ans + c * (c - 1) // 2
		c = 1
		x = a[i]
ans = ans + c * (c - 1) // 2
print(ans)


import sys
from collections import Counter
(n, p, k) = [int(x) for x in sys.stdin.readline().strip().split()]
arr = [int(x) for x in sys.stdin.readline().strip().split()]
brr = [int((x ** 4 - k * x + 100000000 * p) % p) for x in arr]
a = Counter(brr)
print(sum([int(int(a[i]) * (int(a[i]) - 1) / 2) for i in set(brr)]))


import sys
(n, p, k) = map(int, input().split())
a = [int(x) for x in input().split()]
d = {}
res = 0
for c in a:
	v = (c ** 4 - k * c) % p
	if v < 0:
		v += p
	if v in d:
		res += d[v]
		d[v] += 1
	else:
		d[v] = 1
print(res)


(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)