题目描述

给定一个长度为 $N$ 的正整数序列 $A_1, A_2, \ldots, A_N$ 和一个正整数 $K$。

请计算满足以下条件的非空连续子序列的数量：该子序列的元素之和除以 $K$ 的余数等于该子序列的元素个数。注意，即使两个子序列内容相同，只要它们在原序列中的位置不同，就视为不同的子序列。

输入格式

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

$N$ $K$

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

输出格式

输出满足条件的子序列个数。

样例 #1

输入

5 4
1 4 2 3 5

输出

4

样例 #2

输入

8 4
4 2 4 2 4 2 4 2

输出

7

样例 #3

输入

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

输出

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)$共4个。

样例2说明

子序列$(4,2)$被计数4次，$(2,4)$被计数3次。

由DeepSeek翻译。