Extra
Time
BZOJ2274 划分 Time:1s Memory:50M AC:0% Submit:3

Description

给出 n 个数,问有几种划分方案(不能改变数的位置),使得每组中数的 和大于等于 0。输出方案数除以 1000000009 的余数。

Input

* Line 1: A single integer: N N<=100000

* Lines 2..N + 1: Line i + 1 contains a single integer: A_i |A_i|<=100000

Output

* Line 1: A single integer, the number of arrangements modulo 1,000,000,009.

Sample Input

4

2 3 -3 1

Sample Output

4