[USACO11FEB] Generic Cow Protests G

题目描述

Farmer John 的 $N$ 头奶牛($1 \leq N \leq 10^5$)排成一列,正在进行一场抗议活动。第 $i$ 头奶牛的理智度为 $a_i$($-10^4 \leq a_i \leq 10^4$)。 FJ 希望奶牛在抗议时保持理性,为此,他打算将所有的奶牛隔离成若干个小组,每个小组内的奶牛的理智度总和都要不小于零。 由于奶牛是按直线排列的,所以一个小组内的奶牛位置必须是连续的。请帮助 FJ 计算一下,满足条件的分组方案有多少种。

输入输出格式

输入格式


第一行一个整数 $N$。 接下来 $N$ 行,每行一个整数,第 $i$ 行的整数表示第 $i$ 头奶牛的理智度 $a_i$。

输出格式


输出满足条件的分组方案对 $10^9+9$ 取模的结果。

输入输出样例

输入样例 #1

4
2
3
-3
1

输出样例 #1

4

说明

所有合法分组方案如下: - $\texttt{(2 3 -3 1)}$ - $\texttt{(2 3 -3) (1)}$ - $\texttt{(2) (3 -3 1)}$ - $\texttt{(2) (3 -3) (1)}$