Las $N(1<=N<=100,000)$ vacas del Granjero Juan están alineadas en una fila y numeradas $1..N$. Las vacas están llevando a cabo otra de sus extrañas protestas, por lo tanto cada vaca $i$ está llevando un cartel con un entero $A_i(-10,000<=A_i<=10,000)$.

GJ sabe que la muchedumbre vacuna se calmará si ellas están agrupadas apropiadamente y por lo tanto a él le gustaría organizar a las vacas en uno o mas grupos contiguos de tal manera que cada vaca esté en exactamente un grupo y que cada grupo tenga una suma no negativa.

Ayúdelo a contar el número de maneras en que él puede hacer esto, módulo $1,000,000,009$.

Por ejemplo, si $N=4$ y los carteles de las vacas son 2, 3, -3 y 1, entonces las siguientes son las únicas cuatro maneras válidas de organizar a las vacas:

(2 3 -3 1)

(2 3 -3) (1)

(2) (3 -3 1)

(2) (3 -3) (1)

Note que este ejemplo muestra una manera de contar los diferentes ordenamientos de los arreglos.

Entrada

• Línea 1: Un solo entero: $N$

• Líneas 2..N + 1: La línea $i+1$ contiene un solo entero: $A_i$

Salida

• Línea 1: Un solo entero, el número de maneras de organizar módulo $1,000,000,009$.

Ejemplo de Entrada

4
2
3
-3
1

Ejemplo de Salida

4