Day 2: Three Part Harmony

mediumPrefix Sum

You are given an array $$$a$$$ consisting of $$$n$$$ integers: $$$a_1, a_2, \ldots, a_n$$$. Your task is to count the number of ways to partition this array into exactly three contiguous subarrays such that the sum of elements in each subarray is equal.

More formally, you need to find the number of pairs of indices $$$(i, j)$$$ where $$$2 \leq i \leq j \leq n-1$$$, such that: $$$$$$\sum_{k=1}^{i-1} a_k = \sum_{k=i}^{j} a_k = \sum_{k=j+1}^{n} a_k$$$$$$

In other words, the array is split into three parts:

First part: $$$a_1, a_2, \ldots, a_{i-1}$$$
Second part: $$$a_i, a_{i+1}, \ldots, a_j$$$
Third part: $$$a_{j+1}, a_{j+2}, \ldots, a_n$$$

All three parts must have the same sum.

NOTE: Since the answer can be very large, output the result modulo $$$10^9 + 7$$$.

Input Format:

The first line contains a single integer $n$ ($1 \leq n \leq 5 \cdot 10^5$) $\text{---}$ the number of elements in the array. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($|a_i| \leq 10^9$) $\text{---}$ the elements of the array.

Output Format:

Print a single integer $\text{---}$ the number of ways to split the array into three contiguous parts with equal sums.

Constraints:

\[ \begin{align*} &\text{• } n \text{ } (1 \leq n \leq 5 \cdot 10^5) \\ &\text{• } a_1, a_2, \dots, a_n \text{ } (|a_i| \leq 10^9) \end{align*} \]

Examples:

Example 1:

Input:

5
3 -3 0 3 -3

Output:

Example 2: