You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

愚蠢的人类种植了一片花生地, 又到了成熟的季节, 土拨鼠辰辰把这些花生带回去分给鼠小弟们...

同余 - 搜狗百科 (sogou.com)

题面描述

土拨鼠小北希望能够找到分配花生的方案.

$n$ 盒花生排成一排，第 $i$ 个盒子里面有 $a_i$ 个花生。小北打算取连续的几盒，把盒中的花生平均分给 $m$ 个小鼠。小北不希望因分配不均而导致鼠群混乱，因此小北需要做到平均分配，她想知道, 一共有多少种区间 $(l,r)$的选择方案满足如下要求：

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

提示: $a|b$（“|”是整除符号），读作“a整除b”或“b能被a整除”

输入格式

第一行输入两个整数$n, m$

第二行输入$n$个整数表示$a_i$

输出格式

输出一个整数, 表示满足上述条件的$(l, r)$的方案数.

样例 #1

样例输入 #1

3 2
4 1 5

样例输出 #1

3

样例1解释

(1, 1), (2, 3), (1, 3)

样例 #2

样例输入 #2

5 3
1 1 1 1 1

样例输出 #2

3

样例2解释

(1, 3), (2, 4), (3, 5)

数据范围

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