题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

给定一个由 $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
1 1 1 1

1

10
4 -1 2 1 -3 1 2 2 1 3

3

提示

约束条件

• $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 分）无附加约束条件