F - Ultimul Crack

Cerință

Dat fiind un vector de $N$ elemente, putem să facem următoarea operație de câte ori vrem (maxim $N-1$), pornind inițial cu un scor nul:

• Alegem doi indici $i$ și $j$, cu $i < j$, astfel încât $i \oplus j$ ($i$ xor pe biți $j$) sa fie un număr de tipul $k^5$.
• Adăugăm scorului nostru valoarea: $v_i^{v_j} + v_i \cdot v_j + v_j^{v_i}$ modulo P.
• Setăm fie $v_i$ fie $v_j$ cu valoarea $0$, iar indicele setat nu va mai putea fi folosit.

Care este scorul maxim pe care îl putem obține?

Date de intrare

Pe prima linie se găsesc două numere întregi, $N$ și $P$.
Pe următoarea linie se găsește șirul de numere $N$.

Date de ieșire

Pe prima linie se va găsi un singur număr întreg, scorul maxim obținut.

Restricții și precizări

• $1 \leq N \leq 10^5$;
• $1 \leq P, v_i \leq 10^9$;
• Rezultatul final nu se calculează modulo $P$, doar scorurile operaților.

Exemplul 1

stdin

3 4
1 2 3

stdout

3

Explicație

Alegem o singură dată $i=2$, $j=3$ (putem face asta pentru că xor-ul lor este $1$ care este $1^5$). Scorul total va fii deci $2^3+2 \cdot 3+3^2 = 23$ iar sub modul P $=3$. Nu putem obține un scor mai bun.

Exemplul 2

stdin

6 11
4 891 38 19 43 99

stdout

13