문제
-10,000 이상 10,000이하의 N개의 정수로 이뤄진 수열 A = { A1, A2, ..., AN } 이 주어졌을 때, 예쁘게 나누는 방법의 가지수를 세는 프로그램을 작성하라.
여기서 수열을 예쁘게 나누는 방법은 다음과 같다.
● 수열을 한개 이상의 연속된 묶음으로 나눠야 한다.
● 각 수열의 원소는 정확히 하나의 묶음에 속해야 한다.
● 한 묶음에 속한 모든 숫자들의 합은 0이상이어야 한다.
예로 들어 A = { 2, 3, -3, 1 } 일 경우 다음과 같이 총 4가지의 예쁘게 나누는 방법이 존재한다. 괄호로 묶인 부분이 하나의 연속된 묶음을 뜻한다.
1. (2 3 -3 1)
2. (2 3 -3)(1)
3. (2)(3 -3 1)
4. (2)(3 -3)(1)
입력
입력의 첫 줄에는 수열의 개수를 뜻하는 정수 N(1≤N≤100,000)이 입력된다.
그 다음 줄 부터 N개의 줄에는 A1, A2, ..., AN이 입력된다.
출력
입력된 수열 A를 예쁘게 나누는 방법의 가지수를 1,000,000,009로 나눈 나머지를 출력한다.
예제
4
2
3
-3
1
4
로그인해야 코드를 작성할 수 있어요.