该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

本题使用文件输入输出：输入文件名为 period.in，输出文件名为 period.out。

小 Z 的小店连续营业了 $n$ 天，第 $i$ 天的营业额是 $a_i$ 元。

小 Z 想做一次「整数倍促销」复盘：找出所有满足下面两个条件的连续时段 $[l, r]$（$1 \le l \le r \le n$）：

1. 时段的长度 $r - l + 1$ 不超过 $L$；
2. 时段内的营业额总和 $a_l + a_{l+1} + \cdots + a_r$ 是 $k$ 的倍数。

请你求出这样的连续时段一共有多少个。

输入格式

输入文件名为 period.in。

第一行三个整数 $n, k, L$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

输出文件名为 period.out。

一行一个整数，表示满足条件的连续时段的个数。

样例 #1

样例输入 #1

5 3 3
1 2 3 4 5

样例输出 #1

6

样例解释

长度不超过 $3$ 且总和是 $3$ 的倍数的时段有：$[3,3]$（和 $3$）、$[1,2]$（和 $3$）、$[4,5]$（和 $9$）、$[1,3]$（和 $6$）、$[2,4]$（和 $9$）、$[3,5]$（和 $12$），共 $6$ 个。

$[1,5]$ 的和是 $15$，也是 $3$ 的倍数，但长度为 $5$ 超过了 $L = 3$，不算。

样例 #2

样例输入 #2

4 2 4
2 2 2 2

样例输出 #2

10

样例解释

任何一个时段的和都是偶数，$4$ 天共有 $4+3+2+1 = 10$ 个时段。

提示

数据范围

• 对于 $30\%$ 的数据：$n \le 200$；
• 对于 $60\%$ 的数据：$n \le 2 \times 10^5$，$L = n$；
• 对于 $100\%$ 的数据：$1 \le n \le 2 \times 10^5$，$1 \le k \le 10^5$，$1 \le L \le n$，$1 \le a_i \le 10^9$。

提示：答案可能超过 $32$ 位整数的范围。