У Сяо X есть $n$ типов шаров, при этом шаров $i$-го типа имеется $a_i$ штук, и шары одного типа неразличимы. Определим «хаотичность» $f(l, r)$ для шаров с $l$-го по $r$-й типы как количество способов выстроить все эти шары в ряд, взятое по модулю $p$. Сяо X просит вас вычислить значение следующего выражения:
$$ \sum_{l=1}^n \sum_{r=l}^n f(l, r) $$
Входные данные
В первой строке заданы два целых числа $n$ и $p$.
Во второй строке заданы $n$ целых чисел $a_i$.
Выходные данные
Выведите одно целое число — искомый ответ.
Примеры
Пример 1
Входные данные
2 2 1 2
Выходные данные
3
Примечание 1
$$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$$
Пример 2
Входные данные
4 7 1 2 8 9
Выходные данные
28
Пример 3
Входные данные
15 5 1 5 26 1 0 5 0 6 7 51 1 5 26 1 0
Выходные данные
124
Подзадачи
Задача оценивается по системе с группировкой тестов.
- Подзадача 1 (31 балл): $1 \le n \le 5 \times 10^5$, $a_i$ распределены равномерно случайно в диапазоне $[0, 10^5]$, ограничение по времени $1.5 \text{ с}$.
- Подзадача 2 (32 балла): $1 \le n \le 5 \times 10^4$, ограничение по времени $5 \text{ с}$.
- Подзадача 3 (37 баллов): без дополнительных ограничений, ограничение по времени $2.5 \text{ с}$.
Для $100\%$ данных: $1 \le n \le 5 \times 10^5$, $0 \le a_i \le 10^{18}$, $p \in \{2,3,5,7\}$.