問題文

長さ $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$

出力

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

入力例 1

5 4
1 4 2 3 5

出力例 1

4

$(1)$, $(4,2)$, $(1,4,2)$, $(5)$ の $4$ つが条件をみたす部分列です。

入力例 2

8 4
4 2 4 2 4 2 4 2

出力例 2

7

$(4,2)$ が $4$ 回、$(2,4)$ が $3$ 回数えられています。

入力例 3

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

出力例 3

8