Sau khi trả kết quả thi giữa kì, Sóc được mẹ Chinh thưởng cho một phần quà bất ngờ tại cửa hàng đồ chơi. Ở cửa hàng đồ chơi có ~n~ món đồ chơi được đánh số từ trái sang phải. Món quà thứ ~i~ có giá là ~a_i~. Sóc được chọn cho mình phần quà là một đoạn liên tiếp thuộc ~n~ món đồ chơi ban đầu và số lượng món món đồ chơi phải không ít hơn ~l~ và không vượt quá ~r~, đồng thời tổng giá trị của chúng không được vượt quá số ~v~ mà mẹ cho trước.

Yêu cầu: Bạn hãy giúp Sóc đếm xem số cách chọn món quà nhé.

Input

Dòng đầu tiên gồm 4 số là ~n, v, l, r~ (~1\le l\le r \le n \le 10^6, v\le 10^6~) là số lượng món đồ chơi, số tiền tối đa, khoảng giá trị mà số lượng món đồ chơi được chọn

Dòng thứ 2: gồm ~n~ số nguyên không âm ~a_i~ (~a_i \le 10^9~)

Output

Một số nguyên duy nhất là số cách chọn món quà thỏa mãn

Sample Input 1

8 7 4 6
3 5 8 2 6 6 7 7

Sample Output 1

0

Sample Input 2

8 9 2 6
8 6 7 6 1 5 6 7

Sample Output 2

2

Scoring

• Có ~40\%~ số điểm với ~n\le 1000~