题目描述

小 X 有 $n$ 种颜色的球，其中第 $i$ 种颜色的球共有 $a_i$ 个，同色的球无法区分。定义第 $l \sim r$ 种颜色的混乱度 $f(l, r)$ 为：将第 $l \sim r$ 种颜色的所有球排成一排，总共的方案数对 $p$ 取模后的值。小 X 想请你帮忙计算下列式子的值：

输入格式

第一行两个整数 $n, p$。

第二行 $n$ 个整数 $a_i$。

输出格式

一行一个整数，表示答案。

2 2
1 2

3

4 7
1 2 8 9

28

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

124

提示

【样例 1 说明】

本题采用捆绑测试。

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