【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\}$。