1178 - 和为S
Description

小b有一个01序列A,她想知道A有多少个非空连续子序列和为S。

你能帮帮她吗?


Input

第一行输入一个数n,表示A的长度; 第二行输入n个数‘0’或‘1’,表示A中的元素,以空格隔开; 第三行输入一个非负整数S; 其中0≤S≤n≤100000。

Output

输出一个数,表示子数组的个数

Examples

Input

5
1 0 1 0 1
2

Output

4
题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 112
通过次数 30