样例下载

问题描述

有 $N$ 个球迷准备去看球，他们已经排成了一列队伍。每个球迷都有一定的情绪值，第 $i$ 个球迷的情绪值为 $A_i$。可能有的球迷具有负情绪。

球赛主办方准备派若干辆巴士来接送球迷，这些巴士分别编号为 $1, 2, ……$

为了方便乘车，球迷们必须按已经排好的顺序依次上车，即同一辆巴士上的球迷在原队伍中必须是连续的，并且乘坐 $1$ 号车的球迷安排完毕，才安排接下来的球迷乘坐 $2$ 号车，依此类推。另外，尽管巴士非常大，没有限载人数，但如果一辆巴士上的球迷的情绪值之和为负，会有爆发冲突的风险。这显然是主办方所不希望的。

现在主办方让你来安排球迷乘车，要求你确保每辆巴士都不会有爆发冲突的风险。这是一件非常棘手的事情，幸好你是编程高手，你决定先计算一下有多少种不同的乘车方案。

两种乘车方案不同，当前仅当至少存在一个球迷在两种方案中所上车的编号不同。

请你输出乘车的方案数。答案可能很大，你只需要输出答案 $mod$ $1,000,000,009$ 的值。

输入格式

第一行：包含一个整数 $N$。

接下来 $N$ 行，每行一个整数，依次表示 $A_1, A_2, ……, A_N$

输出格式

一个整数，表示答案 $mod$ $1,000,000,009$。

输入样例

3
2
-2
1

输出样例

2

样例解释

乘车方案有两种：

• 三个球迷共乘一辆车
• 前两个球迷共乘一辆车，最后一个球迷乘一辆车

数据范围

100% 的数据：$1 ≤ N ≤ 10^5$, $|A_i| ≤ 10^4$