题目描述

Given are a sequence of $N$ positive integers $A_1, A_2, \ldots, A_N$, and a positive integer $K$.

Find the number of non-empty contiguous subsequences in $A$ such that the remainder when dividing the sum of its elements by $K$ is equal to the number of its elements. We consider two subsequences different if they are taken from different positions, even if they are equal sequences.

给出一个由 $N$ 个正整数 $A_1, A_2, \ldots, A_N$ 和一个正整数 $K$ 组成的序列。

求在 $A$ 中有多少个非空的连续子序列，使得其元素之和除以 $K$ 的余数等于其元素的个数。如果两个子序列取自不同的位置，即使它们是相等的序列，我们也认为它们是不同的。

输入格式

输入内容按以下格式标准输入：

$N$ $K$
$A_1$ $A_2$ $\cdots$ $A_N$

输出格式

打印满足条件的子序列数。

样例 #1

样例输入 #1

5 4
1 4 2 3 5

样例输出 #1

4

样例 #2

样例输入 #2

8 4
4 2 4 2 4 2 4 2

样例输出 #2

7

样例 #3

样例输入 #3

10 7
14 15 92 65 35 89 79 32 38 46

样例输出 #3

8

说明

数据规模与约定

• 所有输入值均为整数。
• $1 \leq N \leq 2\times 10^5$
• $1 \leq K \leq 10^9$
• $1 \leq A_i \leq 10^9$

样例 $1$ 解释

四个序列满足条件： $(1)$ 、 $(4,2)$ 、 $(1,4,2)$ 和 $(5)$ 。

样例 $2$ 解释

$(4,2)$ 被计算四次， $(2,4)$ 被计算三次。