当前没有测试数据。

题目描述

在一个阳光明媚的村庄里，小A有一片美丽的果园。

果园里种着一排果树，这些果树从左到右依次排列，共有 $N$ 棵。每棵果树上都结了许多果实，第 $i$ 棵果树上结了 $A_i$ 个果子。

小明计划在丰收的季节里，从这些果树中挑选一段连续的树，将收获的果子分给村里的 $M$ 个小伙伴。他希望每个小伙伴都能分到同样数量的果子，因此他需要选择一段连续的果树，使得这些树上果子的总数是 $M$ 的倍数。

具体来说，小明需要找到所有可能的区间 $[L, R]$，满足以下条件：

• $1 \le L \le R \le N$，其中 $N$ 是果树的数量。
• 从第 $L$ 棵果树到第 $R$ 棵果树（包含第 $L$ 棵和第 $R$ 棵）的果子总数 $A_L + A_{L+1} + ⋯ + A_R$ 是 $M$ 的倍数。

你的任务是帮助小明计算出，共有多少个这样的区间 $[L, R]$ 满足条件。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示果树的数量和村里小伙伴的数量。

第二行包含 $N$ 个整数 $A_1, A_2, …, A_N$，表示每棵果树上的果子数量。

输出格式

输出一个整数，表示满足条件的区间 $[L, R]$ 的总数。

样例 #1

输入

3 2
4 1 5

输出

3

数据范围

对于 $10\%$ 的数据，满足 $1 \le N \le 100$，$1 \le M \le 10$。

对于另外 $25\%$ 的数据，满足 $1 \le N \le 10^5$，$1 \le M \le 9$。

对于 $100\%$ 的数据，满足 $1 \le N \le 10^5$，$2 \le M \le 10^9$，$1 \le A_i \le 10^9$。