Cho bảng ~C~ các ô vuông đơn vị gồm ~n~ dòng và ~n~ cột. Các dòng được đánh số từ ~1~ đến ~n~, từ trên xuống dưới. Các cột được đánh số từ ~1~ đến ~n~, từ trái sang phải. Ô ở dòng thứ ~i~ và cột thứ ~j~ được gọi là ô ~(i, j)~. Với một dãy số nguyên ~a_1, a_2, ..., a_n~, người ta tiến hành điền vào bảng ~C~ theo quy tắc: Ô ~(i, j)~ sẽ ghi số ~a_i \times a_j~.

Ví dụ: với dãy ~a~ gồm ~5~ số ~a = (2, 4, 1, 5, 3)~ ta có bảng ~C~ như sau:

Một hình chữ nhật con của bảng ~C~ là tập hợp tất cả các ô là giao của một số dòng liên tiếp và một số cột liên tiếp của bảng ~C~.

Yêu cầu

Hãy cho biết có bao nhiêu hình chữ nhật con của bảng ~C~ có tổng giá trị các ô thuộc hình chữ nhật con đó bằng ~k~ cho trước.

Dữ liệu đầu vào

Gồm ba dòng:

• Dòng đầu là ~n~ ~(1 \le n \le 8000)~;
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(0 \le a_i \le 100)~;
• Dòng thứ ba chứa số nguyên ~k~ ~(1 \le k \le 10^6)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số hình chữ nhật con có tổng bằng ~k~.

Ràng buộc dữ liệu

• 40% số điểm tương ứng với các test có ~1 \le n \le 80~;
• 40% số điểm khác tương ứng với các test có ~100 < n \le 800~;
• 20% số điểm còn lại tương ứng với các test có ~n > 800~ và ~a_i > 0~.

Ví dụ

Ví dụ 1

INPUT

5
2 4 1 5 3
30

OUTPUT

12

Giải thích: Có ~12~ hình chữ nhật con có tổng bằng ~30~:

• Giao dòng ~1~ với các cột từ ~1~ tới ~5~;
• Giao các dòng từ ~1~ tới ~5~ với cột ~1~;
• Giao dòng ~1~ và ~2~ với cột ~2~ và ~3~;
• Giao dòng ~1~ và ~2~ với cột ~4~;
• Giao dòng ~5~ với các cột từ ~2~ tới ~4~;
• Giao các dòng từ ~2~ tới ~4~ với cột ~5~;
• Giao dòng ~2~ và ~3~ với cột ~1~ và ~2~;
• Giao dòng ~2~ và ~3~ với cột ~3~ và ~4~;
• Giao dòng ~3~ và ~4~ với cột ~2~ và ~3~;
• Giao dòng ~4~ với cột ~1~ và ~2~;
• Giao dòng ~4~ với cột ~3~ và ~4~;
• Giao dòng ~3~ và ~4~ với cột ~4~.