Description

Farmer John's $N$ cows ($1 \leq N \leq 10^5$) stand in a line, holding a protest. The $i$-th cow has a sanity value $a_i$ ($-10^4 \leq a_i \leq 10^4$).

FJ wants the protest to stay rational. He will partition all cows into several groups so that, in each group, the sum of sanity values is at least zero.

Because the cows stand on a line, cows in one group must occupy a contiguous segment. Please compute how many grouping schemes satisfy the condition.

Input Format

The first line contains an integer $N$.

The next $N$ lines each contain one integer; the $i$-th line gives $a_i$, the sanity value of the $i$-th cow.

Output Format

Output the number of valid grouping schemes modulo $10^9 + 9$.

4
2
3
-3
1

4

Hint

For example, for the sequence $2, 3, -3, 1$, all valid grouping schemes are as follows:

• $\texttt{(2 3 -3 1)}$
• $\texttt{(2 3 -3) (1)}$
• $\texttt{(2) (3 -3 1)}$
• $\texttt{(2) (3 -3) (1)}$

Translated by ChatGPT 5