题目描述

有 $N$ 个盒子从左到右排列在一行中。从左数第 $i$ 个盒子中取出 $A_i$ 个糖果。

你需要将连续的一些盒子中的糖果均匀地分给 $M$ 个孩子。

在这种情况下，找出满足以下条件的数对 $(l, r)$ 的数量：

• $l$ 和 $r$ 都是整数，并满足 $1 \leq l \leq r \leq N$。
• $A_l + A_{l+1} + ... + A_r$ 是 $M$ 的倍数。

约束条件

• 输入中的每个值都是整数。
• $1 \leq N \leq 10^5$
• $2 \leq M \leq 10^9$
• $1 \leq A_i \leq 10^9$

输入

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

$N$ $M$ $A_1$ $A_2$ $...$ $A_N$

输出

打印满足条件的数对 $(l, r)$ 的数量。

请注意，该数量可能不能适应 $32$ 位整数类型。

示例输入 1

3 2
4 1 5

示例输出 1

3

每个数对 $(l, r)$ 对应的 $A_l + A_{l+1} + ... + A_r$ 如下：

• $(1, 1)$ 对应的和为 $4$
• $(1, 2)$ 对应的和为 $5$
• $(1, 3)$ 对应的和为 $10$
• $(2, 2)$ 对应的和为 $1$
• $(2, 3)$ 对应的和为 $6$
• $(3, 3)$ 对应的和为 $5$

其中有三个是 $2$ 的倍数。

示例输入 2

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

示例输出 2

6

示例输入 3

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

示例输出 3

25