余数等于长度

题目描述

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

求 $A$ 的非空连续子序列中，元素和除以 $K$ 的余数等于元素个数的情况数。不过，两个子序列即使作为序列相同，只要取出位置不同，也视为不同。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

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

样例

5 4
1 4 2 3 5

4

$(1)$、$(4,2)$、$(1,4,2)$、$(5)$ 这 $4$ 个是满足条件的子序列。

8 4
4 2 4 2 4 2 4 2

7

$(4,2)$ 被数到 $4$ 次，$(2,4)$ 被数到 $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$