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

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

数据范围：

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

Translated by Eason_AC
2021.12.27