25031번 - Unifying Values 서브태스크

문제

$N$개의 수로 이루어진 수열이 주어진다. 우리는 이 수열을 둘 이상의 연속한 부분으로 나눈 다음 각 부분에 속하는 수들의 합을 구할 수 있다. 이 때, 합을 구한 모든 수가 같아지도록 수열을 나누는 방법의 개수를 구하는 프로그램을 작성하라.

예를 들어 수열이 $[4, -3, 1, 0, 1]$이라고 하자. $[4, -3],ドル $[1],ドル $[0, 1]$의 세 부분으로 나누거나, $[4, -3],ドル $[1, 0],ドル $[1]$의 세 부분으로 나누면 모든 부분의 합이 1ドル$이 된다. 이외의 방법은 없으므로, 이 입력에 대한 답은 2ドル$가 된다.

입력

첫 번째 줄에 하나의 정수 $N$(1ドル ≤ N ≤ 10^4$)이 주어진다.

두 번째 줄에는 수열에 포함된 $N$개의 정수가 공백 하나로 구분되어 순서대로 주어진다. 각 정수는 $-10^{14}$이상 10ドル^{14}$이하의 정수다.

출력

수열을 나누는 방법의 개수를 출력한다. 이 수가 매우 클 수 있으므로, 1ドル,000円,000円,007円$로 나눈 나머지를 출력하도록 한다.

제한

서브태스크

힌트