【XR-4】混乱度
题目描述
小 X 有 $n$ 种颜色的球，其中第 $i$ 种颜色的球共有 $a_i$ 个，同色的球无法区分。定义第 $l \sim r$ 种颜色的混乱度 $f(l, r)$ 为：将第 $l \sim r$ 种颜色的所有球排成一排，总共的方案数对 $p$ 取模后的值。小 X 想请你帮忙计算下列式子的值：
$$ \sum_{l=1}^n \sum_{r=l}^n f(l, r) $$
输入输出格式
输入格式
第一行两个整数 $n, p$。
第二行 $n$ 个整数 $a_i$。
输出格式
一行一个整数，表示答案。
输入输出样例
输入样例 #1
2 2
1 2
输出样例 #1
3
输入样例 #2
4 7
1 2 8 9
输出样例 #2
28
输入样例 #3
15 5
1 5 26 1 0 5 0 6 7 51 1 5 26 1 0
输出样例 #3
124
说明
【样例 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$$
---
**本题采用捆绑测试。**
- Subtask 1（31 points）：$1 \le n \le 5 \times 10^5$，$a_i$ 在 $[0, 10^5]$ 内均匀随机，时限 $1.5 \text{ s}$。
- Subtask 2（32 points）：$1 \le n \le 5 \times 10^4$，时限 $5 \text{ s}$。
- Subtask 3（37 points）：无特殊限制，时限 $2.5 \text{ s}$。
对于 $100\%$ 的数据，$1 \le n \le 5 \times 10^5$，$0 \le a_i \le 10^{18}$，$p \in \{2,3,5,7\}$。