AT_abc378_e.[ABC378E] Mod Sigma Problem

给定一个由 $N$ 个非负整数组成的序列 $A = (A_1, A_2, \dots, A_N)$，以及一个正整数 $M$。

请计算下列值：

$$\sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \bmod M \right)。$$

其中，$X \bmod M$ 表示将非负整数 $X$ 除以 $M$ 后的余数。

输入按以下格式从标准输入给出：

$N$ $M$

$A_1$ $A_2$ $\dots$ $A_N$

输出答案。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $0 \leq A_i \leq 10^9$

样例解释 1

• $A_1 \bmod M = 2$
• $(A_1+A_2) \bmod M = 3$
• $(A_1+A_2+A_3) \bmod M = 3$
• $A_2 \bmod M = 1$
• $(A_2+A_3) \bmod M = 1$
• $A_3 \bmod M = 0$

答案为这些值的和，即 $10$。注意，外层的求和不需要对 $M$ 取模。

由 ChatGPT 4.1 翻译