题目描述

有$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_1A_2...A_N$

输出

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

请注意，该数可能无法适应32位整数类型。

3 2
4 1 5

3

【样例1解释】

每对$(l,r)$的和$A_l,...A_r$如下：

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

其中有三个是2的倍数。

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

提示

输入中的所有数值都是整数。

$1≤N≤10^5$

$2≤M≤10^9$

$1≤A_i≤10^9$