E. Количество пар
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны простое число $$$p$$$, $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$ и целое число $$$k$$$.

Посчитайте количество пар индексов $$$(i, j)$$$ ($$$1 \le i \lt j \le n$$$) для которых $$$(a_i \oplus a_j)(a_i^2 \oplus a_j^2) \equiv k \bmod p$$$.

Здесь $$$\oplus$$$ обозначает побитовую операцию XOR.

Входные данные

Первая строка содержит целые числа $$$n, p, k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$2 \le p \le 10^9$$$, $$$0 \le k \le p-1$$$). Гарантируется, что $$$p$$$ — простое.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le p-1$$$). Гарантируется, что все числа различны.

Выходные данные

Выведите одно число — ответ к задаче.

Примеры
Входные данные
3 3 2
0 1 2
Выходные данные
1
Входные данные
6 11 2
1 3 5 6 7 8
Выходные данные
3
Примечание

В первом примере:

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

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

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

Поэтому только $$$1$$$ пара удовлетворяет условию.

Во втором примере таких пар $$$3$$$: $$$(1, 5)$$$, $$$(1, 6)$$$, $$$(3, 6)$$$.