P2344 [USACO11FEB] Generic Cow Protests G

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.

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 the number of valid grouping schemes modulo $10^9 + 9$.

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