题目描述

有 $N$ 个盒子从左到右排成一排。从左边数起第 $i$ 个盒子中装有 $A_i$ 颗糖果。

你打算从连续的若干个盒子中取出所有的糖果，并把它们平均分给 $M$ 个孩子。

请找出满足以下条件的数对 $(l, r)$ 的数量：

• $l$ 和 $r$ 均为整数，且满足 $1 \le l \le r \le N$；
• $A_l + A_{l+1} + \dots + A_r$ 是 $M$ 的倍数。

输入格式

第一行包含两个正整数 $N$ 和 $M$。

第二行包含 $N$ 个正整数 $A_1, A_2, \dots, A_N$。

输出格式

输出一行，一个整数，表示满足条件的数对 $(l, r)$ 的数量。

样例输入 1

3 2
4 1 5

样例输出 1

3

样例输入 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

说明

样例解释

在第一个样例中，每一对 $(l, r)$ 对应的糖果总和 $A_l + A_{l+1} + \dots + A_r$ 如下：

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

在这些总和中，$4$、$10$ 和 $6$ 是 $2$ 的倍数，共计 $3$ 个。因此输出 $3$。

数据范围

对于所有测试点，保证：

• $1 \le N \le 10^5$。
• $2 \le M \le 10^9$。
• $1 \le A_i \le 10^9$。
• 保证所有的输入值均为整数。