时间限制：1秒　　内存限制：256M

---

【题目描述】

　　由于政府不恰当的医疗政策，该国民众决定进行理智游行，和平表达自己的诉求。
　　组织者决定选取 \(N\) 个人进行排队游行，其中一些人情绪激动，测算下来，排在第 \(i\) 位的人的理智度为 \(a_i\) ，数字可正可负。
　　组织者希望人在抗议时保持理性，为此，他打算将这条队伍分割成几个小组，每个抗议小组的理智度之和必须大于或等于零。队伍已经固定了前后顺序，所以不能交换她们的位置，所以分在一个小组里的人必须是连续位置的。除此之外，分成多少组，每组分多少人，都没有限制。
　　那么有多少种分组的方案呢？

【输入格式】

　　第一行：单个整数 \(N\)。
　　第二行到第 \(N + 1\) 行：第 \(i + 1\) 行有一个整数 \(A_i\)。

【输出格式】

　　输出单个整数：表示分组方案数模 1000000009 的余数

【输入输出样例】

　Input

4
2
3
-3
1

　Output

4

【样例说明】

　　如果分两组，可以把前三人分在一组，或把后三人分在一组；如果分三组，可以把中间两人分在一组，第一和最后一人自成一组；最后一种分法是把四人分在同一组里。

【数据限制】

　　\(100\%\) 的数据满足：\(1 ≤ N ≤ 100000\)，\(−10^5 ≤ a i ≤ 10^5\)。

【来源】

　　Mr.he