糖果分配

题目描述

$N$ 个箱子左右排成一列，从左数第 $i$ 个箱子中装有 $A_i$ 块糖果。

你想从连续的一些箱子中取出糖果，平均分给 $M$ 个孩子。

请计算满足以下条件的数对 $(l, r)$ 的总数：

• $l, r$ 均为整数，且满足 $1 \leq l \leq r \leq N$
• $A_l + A_{l+1} + ... + A_r$ 是 $M$ 的倍数

输入格式

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

$N$ $M$

$A_1$ $A_2$ $...$ $A_N$

输出格式

输出满足条件的数对 $(l, r)$ 的总数。

输出时请注意，结果可能无法放入 $32$ 位整数类型中。

样例

3 2
4 1 5

3

各数对 $(l, r)$ 的和 $A_l + A_{l+1} + ... + A_r$ 如下，其中 $3$ 个是 $2$ 的倍数：

• $(1, 1)$ 的和：$4$
• $(1, 2)$ 的和：$5$
• $(1, 3)$ 的和：$10$
• $(2, 2)$ 的和：$1$
• $(2, 3)$ 的和：$6$
• $(3, 3)$ 的和：$5$

13 17
29 7 5 7 9 51 7 13 8 55 42 9 81

6

10 400000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

25

数据范围

• 输入全部为整数

• $1 \leq N \leq 10^5$

• $2 \leq M \leq 10^9$

• $1 \leq A_i \leq 10^9$