题目描述

有 $n$ 个盒子排成一排，其中左数第 $i$ 个盒子里面有 $a_i$ 个气球。你现在需要从一段连续的盒子当中取出所有的糖果，然后均匀地分给 $m$ 个小朋友。你希望最终每个小朋友手上的糖果数量相同，因此，你思考着有多少组连续的盒子里面的糖果数量是 $m$ 的倍数。形式化地说，你想找到一共有多少个二元组 $(l,r)$ 满足如下要求：

• $1\leqslant l\leqslant r\leqslant n$。
• $\sum\limits_{i=l}^r a_i$ 是 $m$ 的倍数。

数据范围：

• $1\leqslant n\leqslant 10^5$，$2\leqslant m\leqslant 10^9$。
• $1\leqslant a_i\leqslant 10^9$。

输入格式

按照下面形式输入

$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

每对 $(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$ 的倍数。