F - Ultimul Crack

Time limit: 1s Memory limit: 64MB Input: Output:

Cerință

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

  • Alegem doi indici ii și jj, cu i<ji < j, astfel încât iji \oplus j (ii xor pe biți jj) sa fie un număr de tipul k5k^5.
  • Adăugăm scorului nostru valoarea: vivj+vivj+vjviv_i^{v_j} + v_i \cdot v_j + v_j^{v_i} modulo P.
  • Setăm fie viv_i fie vjv_j cu valoarea 00, 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, NN și PP.
Pe următoarea linie se găsește șirul de numere NN.

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

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

Exemplul 1

stdin

3 4
1 2 3

stdout

3

Explicație

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

Exemplul 2

stdin

6 11
4 891 38 19 43 99

stdout

13

Log in or sign up to be able to send submissions!