At UMT University, the Computer Science Club recently held an exciting welcome activity for incoming freshmen, themed Conquering the Entrance Exam Challenge. In a lively atmosphere, the club advisor presented a thought-provoking problem for everyone to brainstorm and discuss together. The enthusiastic club members were given a special square grid C of size ~n×n~. Each row and column in the grid is numbered from 1 to ~n~. In addition, the students were provided with an array of ~n~ integers: ~a_1, a_2, ..., a_n~, representing the learning capabilities of each student in a group. Each cell ~(i, j)~ in the grid is assigned ~a~ value equal to ~a_i × a_j~ , that is, the product of the corresponding capabilities.

For example: with a sequence of 5 numbers ~a~ = (2, 4, 1, 5, 3) we have table C as shown below:

After filling in the grid, the advisor challenged everyone to figure out how many sub-rectangles in the grid have a total sum of exactly ~a~ given integer ~k~. A sub-rectangle is defined as a contiguous block of cells formed by a consecutive group of rows and a consecutive group of columns in the grid. As a future guiding star of the club, you are expected to apply your algorithmic thinking to solve this challenge!

Input

• The first line contains an integer ~n~ - the size of the grid ~(1 ≤ n ≤ 8000)~.

• The second line contains ~n~ integers ~a_1, a_2, ..., a_n (0 ≤ ai ≤ 100)~.

• The third line contains an integer ~k~ ~(1 ≤ k ≤ 10^6)~.

Output

Print a single line containing the number of sub-rectangles in the grid ~C~ whose sum of all elements is exactly ~k~.

Sample Input 1

5
2 4 1 5 3
30

Sample Ouput 1

12