P12708 [KOI 2021 Round 1] 分割

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

给定一个由 $N$ 个整数组成的数列 $A_1, A_2, \ldots, A_N$。我们想将该数列划分为连续的四个部分，每个部分至少包含一个数，且每一部分的数字之和必须相等。 也就是说，存在整数 $i, j, k$（满足 $1 \leq i < j < k < N$），使得将数列划分为以下四段： - $[A_1, \ldots, A_i]$ - $[A_{i+1}, \ldots, A_j]$ - $[A_{j+1}, \ldots, A_k]$ - $[A_{k+1}, \ldots, A_N]$ 例如，若给定的数列是： $$4, -1, 2, 1, -3, 1, 2, 2, 1, 3$$ 若分成以下四段： $$[4, -1, 2], [1, -3, 1, 2], [2, 1], [3]$$ 则每部分的和不同，不符合条件。 若分为： $$[4, -1], [2, 1], [-3, 1, 2, 2, 1], [3]$$ 则每一部分的和都相同，符合条件。 以下划分方式也符合条件： - $[4, -1], [2, 1, -3, 1, 2], [2, 1], [3]$ - $[4, -1, 2, 1, -3], [1, 2], [2, 1], [3]$ 请你编写一个程序，输入数列，计算上述方式下，满足要求的不同划分方法的总数。

第一行输入整数 $N$。 第二行输入 $N$ 个整数 $A_1, A_2, \ldots, A_N$，用空格隔开。

输出满足条件的划分方法总数，占据一行。 （提示：输出结果可能很大，请在 C/C++ 中使用 `long long` 类型，在 Java 中使用 `long` 类型。）

**约束条件** - $4 \leq N \leq 100\,000$ - 对所有 $1 \leq i \leq N$，有 $-1\,000 \leq A_i \leq 1\,000$ **子任务** 1. （5 分）所有 $A_i = 0$ 2. （7 分）所有 $A_i > 0$ 3. （4 分）所有 $A_i \geq 0$ 4. （11 分）$N \leq 10$ 5. （19 分）$N \leq 500$ 6. （23 分）$N \leq 5\,000$ 7. （31 分）无附加约束条件