TouchStone
  Please Login
ログイン 登録
距离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\)