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

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

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

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

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

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

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

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

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

样例 1 说明

果园有 3 棵果树，果子数量分别为 4、1、5，小伙伴数量为 2。小明需要找到所有连续的果树区间，使得这些树上的果子总数是 2 的倍数。

具体分析如下：

• 区间 [1, 1]：只有第 1 棵树，果子总数 4，是 2 的倍数。
• 区间 [1, 2]：第 1 到第 2 棵树，果子总数 4 + 1 = 5，不是 2 的倍数。
• 区间 [1, 3]：第 1 到第 3 棵树，果子总数 4 + 1 + 5 = 10，是 2 的倍数。
• 区间 [2, 2]：只有第 2 棵树，果子总数 1，不是 2 的倍数。
• 区间 [2, 3]：第 2 到第 3 棵树，果子总数 1 + 5 = 6，是 2 的倍数。
• 区间 [3, 3]：只有第 3 棵树，果子总数 5，不是 2 的倍数。

因此，满足条件的区间有 [1, 1]、[1, 3]、[2, 3]，总数为 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 \leq N \leq 10^5，2 \leq M \leq 10^9，1 \leq A_i \leq 10^9。

月赛前缀和同余定理25年3月