Cho một mảng a gồm n số nguyên, các phần tử có thể âm, dương hoặc bằng 0.

• Một đoạn con là dãy liên tiếp [~a_l, a_{l+1}, …, a_r~] với ~1 ≤ l ≤ r ≤ n~.
• Tính số đoạn con sao cho tổng = ~K~.

Nhiệm vụ: đếm số đoạn con có tổng bằng ~K~.

Input

• Dòng 1: ~n~ — số phần tử trong mảng (~1 ≤ n ≤ 2×10^5~)
• Dòng 2: ~a[1] a[2] … a[n]~ — mảng số nguyên: ~-10^9 ≤ a[i] ≤ 10^9~
• Dòng 3: ~K~ — tổng cần tìm, ~-10^{14} ≤ K ≤ 10^{14}~

Output

• Một số nguyên: số đoạn con có tổng bằng ~K~

Ví dụ

Input:

5
1 2 1 3 2
3

Output:

3

Giải thích:

Các đoạn con có tổng = 3:

[1,2] → tổng = 3

[2,1] → tổng = 3

[3] → tổng = 3