TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P4969
  • 题目
  • P4969抗议
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1S,256M
    问题描述

    约翰家的N 头奶牛正在排队游行抗议。一些奶牛情绪激动,约翰测算下来,排在第i 位的奶牛的理智度为Ai,数字可正可负。
    约翰希望奶牛在抗议时保持理性,为此,他打算将这条队伍分割成几个小组,每个抗议小组的理智度之和必须大于或等于零。奶牛的队伍已经固定了前后顺序,所以不能交换它们的位置,所以分在一个小组里的奶牛必须是连续位置的。除此之外,分组多少组,每组分多少奶牛,都没有限制。

    约翰想知道有多少种分组的方案,由于答案可能很大,只要输出答案除以1000000009 的余数即可。

    输入格式

    第一行:单个整数N
    接下来N行,每行有一个整数Ai。

    输出格式

    一个整数:表示分组方案数模1000000009 的余数

    样例输入 1

    4
    2
    3
    -3
    1

    样例输出 1

    4

    样例输入 2

    9
    10
    7
    -4
    -8
    8
    3
    4
    10
    10

    样例输出 2

    88

    提示

    【样例1说明】

    如果分两组,可以把前三头分在一组,或把后三头分在一组;如果分三组,可以把中间两头分在一组,第一和最后一头奶牛自成一组;最后一种分法是把四头奶牛分在同一组里。

    对于50% 的数据,1<= N <=200

    对于100%的数据,\(1 ≤ N ≤ 10^5\)
    \(−10^5 ≤ Ai ≤ 10^5\)