Generic Cow Protests

题目描述

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 取模的结果。

样例

提示

所有合法分组方案如下：

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

来源

USACO