N개의 정수 수열 A₁, A₂, ..., A_N이 주어진다.

수열을 각각이 연속된 네 부분으로 나누려고 한다.

단, 각 부분은 최소 하나의 수를 포함해야 한다.

또, 각 부분의 합은 모두 같아야 한다.

즉, 어떤 i, j, k(1 ≤ i < j < k < N)에 대해서 [A₁, ...A_i], [A_i+1, ... A_j], [A_j+1, ... A_k], A[_k+1,...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 ≤​ N ≤​ 100,000

* 모든 1 ≤ i ≤ N에 대해 -1,000 ≤​ A_i ≤​ 1,000

[부분 문제]

1.​ (5점) 모든​ 1 ≤ i ≤ N에 대해​  A_i ​= 0

2. (7점) 모든​ 1 ≤ i ≤ N에 대해​  A_i ​> 0​

3.​ (4점) 모든​ 1 ≤ i ≤ N에 대해​  A_i ​≥ 0​

4.​ (11점)​ N ≤ 10​ 

5.​ (19점)​ N ≤ 500 

6.​ (23점) N ≤ 5,000 

7.​ (31점) 추가 제약 조건 없음

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

두 번째 줄에 N개의 정수 A₁, A₂, ..., A_N​이 공백 하나씩을 사이로 두고 주어진다.

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

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