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