配点 : $500$ 点

問題文

長さ $N$ の正整数列 $A_1, A_2, \ldots , A_N$ と正の整数 $K$ が与えられます。

$A$ の空でない連続する部分列であって、要素の和を $K$ で割った余りが要素の数と等しくなるものの数を求めてください。ただし、$2$ つの部分列が列として同じでも、取り出す位置が異なるならば区別するものとします。

制約

• 入力は全て整数である。
• $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$

出力

条件をみたす部分列の個数を出力してください。

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