题目描述

张三准备了 n 个装有糖果的盒子，排成一列，其中从左数起第 i 个盒子里面有 a$_i$ 个糖果。

张三现在需要从一段连续的盒子当中取出所有的糖果，然后均匀地分给 m 个小朋友，即最终每个小朋友手上的糖果数量相同。

请问张三有多少种不同的选择方案。

输入格式

第一行输入 n 和 m, 分别表示盒子数和小朋友数。

接下来一行输入 n 个整数，分别表示每个盒子内的糖果数。

输出格式

输出合法的取糖果方案数。

样例

输入输出样例

输入样例#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<=N<=10$^5$

• 2<=M<=10$^{10}$

• 1<=A$_i$<=10$^9$