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 翻译