P5598 【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) $$

无

无

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