Cho dãy số nguyên không âm ~A = (a_1, a_2, \dots, a_n)~.

Yêu cầu: Với hai số nguyên ~k, S~ cho trước, hãy đếm xem trong dãy ~A~ có bao nhiêu đoạn con ~(a_l, a_{l+1}, a_{l+2}, \dots, a_r)~ thỏa mãn đồng thời các điều kiện sau:

• Giá trị ~r - l + 1~ (độ dài của đoạn con) là một số nguyên chia hết cho ~k~;

• Giá trị ~a_l + a_{l+1} + a_{l+2} + \dots + a_r~ (tổng các phần tử của đoạn con) không nhỏ hơn ~S~.

Input

• Dòng 1: ba số nguyên ~n, k, S~ ~(1 < k < n \le 10^6; 0 \le S \le 10^{15})~;

• Dòng 2: ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(0 \le a_i \le 10^6, \forall i = 1, 2, \dots, n)~.

Output

Một số nguyên là số lượng đoạn con đếm được theo yêu cầu đề bài.

Scoring

Sample Input 1

5 2 15
3 2 5 9 7

Sample Output 1

3

Notes

~3~ đoạn con ~[3\ 2\ 5\ 9], [2\ 5\ 9\ 7], [9\ 7]~ có tổng tương ứng là: ~19, 23, 16~.