题目描述

There are $N$ boxes arranged in a row from left to right. The $i$-th box from the left contains $A_i$ candies.

You will take out the candies from some consecutive boxes and distribute them evenly to $M$ children.

Such being the case, find the number of the pairs $(l, r)$ that satisfy the following:

• $l$ and $r$ are both integers and satisfy $1 \leq l \leq r \leq N$.
• $A_l + A_{l+1} + ... + A_r$ is a multiple of $M$.

有 $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$ （位）整数类型。

样例 #1

样例输入 #1

3 2
4 1 5

样例输出 #1

3

样例 #2

样例输入 #2

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

样例输出 #2

6

样例 #3

样例输入 #3

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

样例输出 #3

25

说明

数据规模与约定

• 所有输入值均为整数。
• $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} + ... + A_r$ 如下：

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

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