Вам даны простое число \(p\), \(n\) чисел \(a_1, a_2, \ldots, a_n\) и целое число \(k\).
Посчитайте количество пар индексов \((i, j)\) (\(1 \le i < j \le n\)) для которых \((a_i + a_j)(a_i^2 + a_j^2) \equiv k \bmod p\).
Выходные данные
Выведите одно число — ответ к задаче.
Примечание
В первом примере:
\((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\).
Поэтому только \(1\) пара удовлетворяет условию.
Во втором примере таких пар \(3\): \((1, 5)\), \((2, 3)\), \((4, 6)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 0
0 1 2
|
1
|
|
2
|
6 7 2
1 2 3 4 5 6
|
3
|