题目描述

$\red{Farmer John }$的 $\red{N (1 <= N <= 100,000) }$头奶牛排成一排，编号为 $\red{1..N}$。奶牛们正在进行另一场奇怪的抗议，所以每头奶牛 $\red{i }$都举着一个带有整数 $\red{A_i(-10,000 <= A_i <= 10,000) }$的标志。

$\red{FJ }$知道，如果奶牛群被适当地分组，它们会表现得很好，因此希望将奶牛排列成一个或多个连续的组，以便每头奶牛都在一个组中，并且每个组都有一个非负的总和。

帮助他计算可以做到这一点的方法的数量，以 $\red{1,000,000,009 }$为模。

举例来说，如果 $\red{N = 4 }$并且奶牛的符号是 $\red{2}$、$\red{3}$、$\red{-3 }$和$\red{1，}$那么以下是仅有的四种有效的 奶牛排列方式：

(2 3 -3 1)
(2 3 -3) (1)
(2) (3 -3 1)
(2) (3 -3) (1)

注意这个例子演示了计算 排列的不同顺序的规则。

给出$\red{n}$个数，问有几种不同的位置）方案，每组中数的和除数大于$\red{0}$。

输入格式

第 $\red{1 }$行：单个整数：$\red{N}$

第 $\red{2..N + 1 }$行：第 $\red{i + 1 }$行包含单个整数：$\red{A_i}$

输出格式

第 $\red{1 }$行：单个整数，排列数模 $\red{1,000,000,009}$。

样例

输入样例

4
2
3
-3
1

输出样例

4