Một hệ thống lưu trữ năng lượng bao gồm một dãy các mô-đun pin có công suất sạc khác nhau. Khi hệ thống hoạt động, các mô-đun pin này sạc vào một bộ lưu trữ trung tâm. Hệ thống cần kiểm tra xem có thể tạo ra chính xác K đơn vị năng lượng từ một số mô-đun pin liên tiếp hay không. Mỗi lần đạt được đúng 𝐾, hệ thống sẽ kích hoạt một chế độ xả pin đặc biệt giúp tối ưu hóa hiệu suất lưu trữ.

Yêu cầu: Cho một dãy n mô-đun pin, mỗi mô-đun có một mức năng lượng sạc nhất định. Hãy đếm số cách chọn một đoạn liên tiếp của các mô-đun pin sao cho tổng năng lượng của đoạn đó bằng đúng 𝐾. Giả sử có một hệ thống với mức năng lượng sạc của các mô-đun như sau: [50, 20, 30, 40, 10] Và cần tìm những đoạn có tổng năng lượng bằng 𝐾 = 50. Khi đó, có 3 cách đạt được tổng năng lượng đúng bằng 𝐾:

• Chọn mô-đun thứ 1: [50]

• Chọn mô-đun thứ 2 và 3: [20, 30]

• Chon mô-đun thứ 4 và 5: [40, 10]

Dữ liệu: đọc từ thiết bị chuẩn (bàn phím)

• Dòng đầu tiên chứa số nguyên dương n là số mô-đun pin (1 ≤ 𝑛 ≤ 10^5)

• Dòng thứ hai chứa n số nguyên, các số cách nhau một dấu cách là số đơn vị năng lượng của n mô-đun pin. Giá trị các số không quá 10^6

• Dòng thứ ba chứa số nguyên 𝐾 (1 ≤ 𝐾 ≤ 10^12)

Kết quả: Ghi ra thiết bị chuẩn (màn hình) là số cách chọn một đoạn liên tiếp có tổng bằng K.

Input:

5
50 20 30 40 10
50

Output:

3

Ràng buộc:

• Có 30% số điểm thỏa n ≤ 500

• Có 30% số điểm thỏa 500 < n ≤ 5000

• Có 40% số điểm thỏa 5000 < n ≤ 10^5