题目描述
农场主John的N（1≤N≤105） 头奶牛正在排队游行抗议。一些奶牛情绪激动，John测算下来，排在第i 位的奶牛的理智度为ai（-104≤ai≤104）。John希望奶牛在抗议时保持理性，为此，他打算将所有奶牛分割成几个小组，每个抗议小组的理智度之和都要不小于零。奶牛的队伍已经固定了前后顺序，所以不能交换它们的位置，所以分在一个小组里的奶牛的位置必须是连续的。除此之外，分组多少组，每组分多少奶牛，都没有限制。John想知道有多少种分组的方案，由于答案可能很大，只要输出答案除以1000000009 的余数即可。
输入
第一行：单个整数N，1 ≤ N ≤ 100000
第二行到第N + 1 行：第i + 1 行有一个整数ai，-104≤ai≤104 。
输出
单个整数：表示分组方案数模109+9 的余数
提示
本题是P2344
说明
解释:如果分两组，可以把前三头分在一组，或把后三头分在一组；
如果分三组，可以把中间两头分在一组，第一和最后一头奶牛自成一组；最后一种分法是把四头奶牛分在同一组里。