桃园里面有 n 个人在摘桃子。现在 n 个人排成一排,从左到右每个人拥有的桃子数是 ai。 桃园里有一个免费获得桃子的规则,如果连续 x 个人的桃子总数除以 k 的余数正好是 x, 那么这 x 个人就可以免费获得桃子,并且每天只有一次免费获得桃子的机会。
请聪明的你算出一共有多少种不同的方案可以使今天有人免费获得桃子。
输入格式
第一行两个数字 n 、k。
接下来一行 n 个整数 a1,a2,…,an。
输出格式
一个数,表示答案。
样例输入
8 4
4 2 4 2 4 2 4 2
样例输出
7
NOTE
七个不同方案分别是:
a1,a2 、 a2,a3 、a3,a4 、a4,a5 、 a5,a6 、a6,a7 、a7,a8。
注:只要子串有一个边界不同即为不同的方案
数据规模
所有数据保证 1≤n≤2×105,1≤k≤109,1≤ai≤109。