小 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
样例 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
样例 2 输出
28
样例 3 输入
15 5 1 5 26 1 0 5 0 6 7 51 1 5 26 1 0
样例 3 输出
124
子任务
本题采用捆绑测试。
- 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\}$。