有 $N$ 个盒子排成一排，第 $i$ 个盒子里有 $A_i$ 个糖果。你需要从一些连续的盒子里取出糖果，分给 $M$ 个小朋友，使得每个小朋友得到的糖果数量相等。求有多少种取法满足以下两个条件：

• 取出的盒子数为 $r-l+1$，其中 $1\le l\le r\le N$。
• 分给每个小朋友的糖果数量是 $K$ 的倍数，其中 $K=\frac{{\sum }_{i=l}^r{A}_i}{M}$。

输入格式

第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个整数 $A_1,A_2,\dots ,A_N$。

输出格式

输出一个整数，表示满足条件的取法数。

数据范围

• $1\le N\le 10^5$，
• $1\le M\le 10$，
• $1\le A_i\le 10^9$。

输入样例1：

3 2
4 1 5

输出样例1：

3

输入样例2：

13 17
29 7 5 7 9 51 7 13 8 55 42 9 81

输出样例2：

6

输入样例3：

10 400000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

输出样例3：

25

提示

样例1解释：

符合条件的取法有 $(1,3),(2,3),(3,3)$。

样例2解释：

符合条件的取法有 $(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)$。

样例3解释：

符合条件的取法有 $(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(1,10),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(2,10),(3,3),(3,4),(3,5),(3,6),(3,7)$。