소들의 시위 그룹 나누기

농부 John의 소 $N$마리($1 \le N \le 100{,}000$)가 한 줄로 서 있고, 왼쪽부터 $1$번부터 $N$번까지 번호가 매겨져 있습니다. 소들이 또 이상한 시위를 벌이고 있어서, 각 소 $i$는 정수 $A_i$($-10{,}000 \le A_i \le 10{,}000$)가 적힌 팻말을 들고 있습니다.

John은 소들을 적절히 묶어 두면 소란이 가라앉는다는 것을 알고 있습니다. 그래서 모든 소를 하나 이상의 연속한 그룹으로 나누려고 합니다. 이때 모든 소는 정확히 하나의 그룹에만 속해야 하고, 각 그룹에 속한 소들이 든 정수의 합은 $0$ 이상이어야 합니다.

John이 소들을 이렇게 나눌 수 있는 방법의 수를 $1{,}000{,}000{,}009$로 나눈 나머지를 구하세요.

두 방법은 그룹의 경계가 서로 다르면 서로 다른 방법으로 셉니다.

• 첫째 줄: 정수 $N$이 주어집니다.
• 둘째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄에 정수 $A_i$가 하나씩 주어집니다.

• 첫째 줄: 소들을 나누는 방법의 수를 $1{,}000{,}000{,}009$로 나눈 나머지를 출력합니다.