concurs "Bagae" | prosum

Se dau $N$ numere naturale $a_1$, $a_2$, $\dots$, $a_N$ şi un număr natural nenul $M$.

Cerința

Să se determine numărul perechilor de indici $(i, j)$, cu $i < j$, cu proprietatea că numărul $a_i \cdot a_j + a_i + a_j$ este divizibil cu $M$.

Date de intrare

Fișierul de intrare prosum.in conține pe prima linie numerele naturale $N$ și $M$, iar pe următoarea linie cele $N$ numere naturale $a_1, a_2, \dots a_N$, separate prin spațiu.

Date de ieșire

Fișierul de ieșire prosum.out va conține pe prima linie numărul perechilor de indici $(i, j)$, cu $i < j$, cu proprietatea că numărul $a_i \cdot a_j + a_i + a_j$ este divizibil cu $M$.

Restricții și precizări

• $2 \leq N \leq 100 \ 000$
• $0 \leq a_i \leq 10^{18}$; $\forall i \in \{1, 2, ..., n \}$
• $1 \leq M \leq 10^{17}$
• Pentru teste în valoare de $23$ puncte: $2 \leq N \leq 5 \ 000$, $0 \leq a_i \leq 10^9$; $1 \leq M \leq 10^9$
• Pentru alte teste în valoare de $13$ puncte: $2 \leq N \leq 1 \ 000$
• Pentru alte teste în valoare de $33$ puncte: $0 \leq a_i \leq 10^9$; $1 \leq M \leq 10^9$, iar numerele $a_i$ au în scrierea binară cel mult $3$ cifre egale cu $1$.
• Pentru alte teste în valoare de $31$ puncte: nu avem alte restricții.

Exemplul 1

prosum.in

4 13
6 15 6 1

prosum.out

2

Explicație

Există două perechi de indici având proprietatea cerută, $(1, 4)$ și $(3, 4)$, deoarece avem $6 \cdot 1 + 6 + 1 = 13$, care este divizibil cu $M = 13$.