AT_abc105_d [ABC105D] Candy Distribution

有 $N$ 个箱子从左到右排成一列，第 $i$ 个箱子里有 $A_i$ 个糖果。 你想从若干连续的箱子中取出糖果，并将它们平均分给 $M$ 个孩子。 请你计算满足以下条件的所有组 $(l, r)$ 的总数： - $l, r$ 都是整数，且满足 $1 \leq l \leq r \leq N$。 - $A_l + A_{l+1} + \cdots + A_r$ 是 $M$ 的倍数。

输入通过标准输入按以下格式给出。 > $N$ $M$ $A_1$ $A_2$ $\cdots$ $A_N$

输出满足条件的组 $(l, r)$ 的总数。 请注意，输出结果可能超出 $32$ 位整数范围。

### 限制条件 - 所有输入均为整数。 - $1 \leq N \leq 10^5$ - $2 \leq M \leq 10^9$ - $1 \leq A_i \leq 10^9$ ### 样例解释 1 对于每组 $(l, r)$，其和 $A_l + A_{l+1} + \cdots + A_r$ 如下，其中有 $3$ 组是 $2$ 的倍数。 - $(1, 1)$ 的和：$4$ - $(1, 2)$ 的和：$5$ - $(1, 3)$ 的和：$10$ - $(2, 2)$ 的和：$1$ - $(2, 3)$ 的和：$6$ - $(3, 3)$ 的和：$5$ 由 ChatGPT 4.1 翻译