Mały X ma $n$ rodzajów kul, przy czym kul $i$-tego rodzaju jest łącznie $a_i$, a kule tego samego koloru są nierozróżnialne. Definiujemy nieład $f(l, r)$ dla kolorów od $l$ do $r$ jako: liczbę sposobów na ustawienie wszystkich kul o kolorach od $l$ do $r$ w jednym rzędzie, modulo $p$. Mały X prosi Cię o obliczenie wartości poniższego wyrażenia:

$$ \sum_{l=1}^n \sum_{r=l}^n f(l, r) $$

Wejście

Pierwsza linia zawiera dwie liczby całkowite $n, p$.

Druga linia zawiera $n$ liczb całkowitych $a_i$.

Wyjście

Wypisz jedną liczbę całkowitą oznaczającą wynik.

Przykład

Przykład 1

Wejście:

2 2
1 2

Wyjście:

3

Uwagi

$$f(1,1) = 1 \bmod 2 = 1$$

$$f(1,2) = 3 \bmod 2 = 1$$

$$f(2,2) = 1 \bmod 2 = 1$$

$$ \sum_{l=1}^n \sum_{r=l}^n f(l, r) = 3$$

Przykład 2

Wejście:

4 7
1 2 8 9

Wyjście:

28

Przykład 3

Wejście:

15 5
1 5 26 1 0 5 0 6 7 51 1 5 26 1 0

Wyjście:

124

Podzadania

Zadanie oceniane jest w systemie pakietowym.

• Podzadanie 1 (31 punktów): $1 \le n \le 5 \times 10^5$, $a_i$ losowane jednostajnie z przedziału $[0, 10^5]$, limit czasu $1.5 \text{ s}$.
• Podzadanie 2 (32 punkty): $1 \le n \le 5 \times 10^4$, limit czasu $5 \text{ s}$.
• Podzadanie 3 (37 punktów): brak dodatkowych ograniczeń, limit czasu $2.5 \text{ s}$.

Dla $100\%$ danych wejściowych: $1 \le n \le 5 \times 10^5$, $0 \le a_i \le 10^{18}$, $p \in \{2,3,5,7\}$.