题目描述

给定一系列 $N$ 个正整数 $A_1, A_2, \\ldots, A_N$，以及一个正整数 $K$。

找出满足以下条件的非空连续子序列的数量：其元素之和除以 $K$ 的余数等于子序列的元素个数。即使两个子序列相等，如果它们来自不同的位置，也视为不同的子序列。

约束条件

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

输入

输入数据从标准输入读取，其格式如下：

$N$ $K$

$A_1$ $A_2$ $\\cdots$ $A_N$

输出

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

示例输入 1

5 4
1 4 2 3 5

示例输出 1

4

满足条件的子序列有四个：$(1)$，$(4,2)$，$(1,4,2)$ 和 $(5)$。

示例输入 2

8 4
4 2 4 2 4 2 4 2

示例输出 2

7

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

示例输入 3

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

示例输出 3

8