P0788

[Usaco2011 Feb]Generic Cow Protests

[Usaco2011 Feb]Generic Cow Protests

Farmer John 的 NN 头奶牛排成一列，依次编号为 1,2,…,N1,2,\ldots,N。奶牛们正在进行一场抗议，第 ii 头奶牛举着一个写有整数 AiA_i 的牌子。

为了维持秩序，Farmer John 希望将这些奶牛划分成一个或多个连续的组，使每头奶牛恰好属于一个组，并且每组中所有奶牛所举数字之和均为非负数。划分时不能改变奶牛的相对位置。

请计算满足条件的划分方案数，并输出其对 109+910^9+9 取模后的结果。

输入格式

第一行输入一个整数 NN，表示奶牛的数量。

接下来 NN 行，第 ii 行输入一个整数 AiA_i，表示第 ii 头奶牛所举牌子上的数字。

输出格式

输出一个整数，表示满足条件的划分方案数对 109+910^9+9 取模后的结果。

样例输入

4
2
3
-3
1

样例输出

4

样例解释

对于数列 2,3,−3,12,3,-3,1，共有以下 44 种合法的划分方案：

  • (2,3,−3,1)(2,3,-3,1)；
  • (2,3,−3)∣(1)(2,3,-3)\mid(1)；
  • (2)∣(3,−3,1)(2)\mid(3,-3,1)；
  • (2)∣(3,−3)∣(1)(2)\mid(3,-3)\mid(1)。

数据范围

  • 1≤N≤1051\le N\le 10^5；
  • −104≤Ai≤104-10^4\le A_i\le 10^4。

来源与许可

本题为 USACO 20112011 年 22 月竞赛试题「Generic Cow Protests」，题面与测试数据整理自 BZOJ 22742274。

样例 1

输入

4
2
3
-3
1

输出

4