摘桃子

题目描述

桃园里面有 $n$ 个人在摘桃子。现在 $n$ 个人排成一排，从左到右每个人拥有的桃子数是 $a_i$。 桃园里有一个免费获得桃子的规则，如果连续 $x$ 个人的桃子总数除以 $k$ 的余数正好是 $x$, 那么这 $x$ 个人就可以免费获得桃子,并且每天只有一次免费获得桃子的机会。 请聪明的你算出一共有多少种不同的方案可以使今天有人免费获得桃子。

输入格式

第一行两个数字 $n$ 、$k$。

接下来一行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

一个数，表示答案。

样例输入

8 4
4 2 4 2 4 2 4 2

样例输出

7

样例解释

七个不同方案分别是: $a_1, a_2$ 、 $a_2, a_3$ 、$a_3, a_4$ 、$a_4, a_5$ 、 $a_5, a_6$ 、$a_6, a_7$ 、$a_7, a_8$。 注：只要子串有一个边界不同即为不同的方案

数据范围

所有数据保证 $1\leq n\leq 2 × 10^5, 1 \leq k \leq 10^9, 1 \leq a_i \leq 10^9$。