Division

You are given a sequence of $N$ integers $A_1, A_2, \dots, A_N$. You want to split the sequence into four contiguous parts. Each part must contain at least one number, and the sums of the four parts must all be equal. That is, for some $i, j, k$ ($1 \le i < j < k < N$), split the sequence into $[A_1, \dots, A_i], [A_{i+1}, \dots, A_j], [A_{j+1}, \dots, A_k], [A_{k+1}, \dots, A_N]$.

For example, suppose the given sequence is $4, -1, 2, 1, -3, 1, 2, 2, 1, 3$. If you split it as below, the sums of the parts differ, so this form is not allowed.

$[4, -1, 2], [1, -3, 1, 2], [2, 1], [3]$

If you split it as below, the sums of all parts are equal.

$[4, -1], [2, 1], [-3, 1, 2, 2, 1], [3]$

The splits below also give equal sums for all parts.

$[4, -1], [2, 1, -3, 1, 2], [2, 1], [3]$ or $[4, -1, 2, 1, -3], [1, 2], [2, 1], [3]$

Write a program that reads the sequence and counts the number of possible ways to split it as above.

The first line gives the length of the sequence, $N$.

The second line gives the $N$ integers $A_1, A_2, \dots, A_N$, separated by single spaces.

Print the number of possible ways on the first line.

The answer can be very large, so in C and C++ you must use a variable of type long long, and in Java a variable of type long.

• $4 \le N \le 100\,000$
• For all $1 \le i \le N$, $-1\,000 \le A_i \le 1\,000$