Республиканская олимпиада по информатике 2019 года за 9 класс | Казахстанские олимпиады

Задача A. Найдите все пары

Дано простое $P$, натуральное $n$ и массив $a$ размера $n$. Назовем пару чисел хорошими если их произведение дает такой же остаток при делении на $P$ что и сумма. Более формально, если выполняется условие $(x * y) mod P = (x + y) mod P$ то пара $(x, y)$ считается хорошей. Найдите количество хороших пар в массиве.

Формат входного файла

В первой строке входного файла заданы два целых числа $n$ $(1 <= n <= 10^5)$ — количество чисел в массиве, $P$ $(2 <= P <= 10^9)$ — заданное простое число $P$. Во второй строке входного файла заданы $n$ чисел $a_i$ $(0 <= a_i <= 10^9)$ - $i$-число в массиве.

Формат выходного файла

Выведите одно целое число - количество хороших пар в массиве.

Примеры

Вход

4 3
3 5 12 11

Выход

2

Вход

3 5
1 2 7

Выход

1