나누기

$ N $개의 정수 수열 $ A_1, A_2, \ldots, A_N $이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또, 각 부분의 합은 모두 같아야 한다. 즉, 어떤 $ i $, $ j $, $ k $($ 1 \le 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] $

수열을 입력 받아 위와 같이 나눌 수 있는 가능한 방법의 개수를 계산하는 프로그램을 작성하라.

• $ 4 \le N \le 100\,000 $
• 모든 $ 1 \le i \le N $에 대해 $ -1\,000 \le A_i \le 1\,000 $

1. (5점) 모든 $ 1 \le i \le N $에 대해 $ A_i = 0 $
2. (7점) 모든 $ 1 \le i \le N $에 대해 $ A_i > 0 $
3. (4점) 모든 $ 1 \le i \le N $에 대해 $ A_i \ge 0 $
4. (11점) $ N \le 10 $
5. (19점) $ N \le 500 $
6. (23점) $ N \le 5\,000 $
7. (31점) 추가 제약 조건 없음

첫 번째 줄에 수열의 길이 $ N $이 주어진다.

두 번째 줄에 $ N $개의 정수 $ A_1, A_2, \ldots, A_N $이 공백 하나씩을 사이로 두고 주어진다.

첫 번째 줄에 가능한 방법의 개수를 출력한다.

출력 값이 매우 클 수 있으므로 C, C++ 언어에서는 “long long` 형의 변수를, Java에서는 `long“ 형의 변수를 사용해야 한다.