题目描述

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

求出满足以下条件的 $A$ 的非空连续子序列的数量:将子序列的元素之和除以 $K$ 的余数等于子序列的元素个数。

即使两个序列相等，只要它们的位置不同，我们也认为它们是不同的子序列。

输入

第一行两个整数$N,K$

第二行一共$N$个整数，表示$A$序列

输出

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

5 4
1 4 2 3 5

4

样例解释

满足条件的子序列有:(1),(4,2),(1,4,2)和(5)。

8 4
4 2 4 2 4 2 4 2

7

样例解释

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

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$