题目描述

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

• $1\leqslant l\leqslant r\leqslant n$。
• $\sum\limits_{i=l}^r a_i\mid m$。

输入格式

第一行两个正整数 $n, m$，$1\leqslant n\leqslant 10^5$，$2\leqslant m\leqslant 10^9$。

第二行 $N$ 个正整数 $a_i$，$1\leqslant a_i\leqslant 10^9$。

输出格式

满足要求的二元组数。

3 2
4 1 5

3

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