Luka ha construido un relieve consistente de una larga línea de ~n~ columnas de alturas enteras no negativas. La altura de todas las columnas era inicialmente cero. El relieve fue construido por pasos, donde en cada paso Luka seleccionaría una secuencia contigua de columnas con iguales alturas y elevaría todas en la subsecuencia por uno, excepto la primera y la última.

Cientos de años han pasado y algunas de las columnas han sido robadas. Un descendiente de Luka está tratando de determinar el número de posibles relieves que pueden haber sido construidos por Luka tal que las alturas de las columnas restantes concuerden con el relieve original.

Entrada

La primera línea de la entrada contiene el entero positivo ~n (1 \leq n \leq 10 000) ~, el número de columnas en el relieve de Luka. La segunda línea de la entrada contiene ~n~ enteros ~hi (-1 \leq h \leq 10 000)~, las alturas de las columnas separados entre sí por espacio. Una altura de ~-1~ representa una columna robada.

Salida

La primera y única línea de la salida tiene que contener el número requerido de posibles relieves modulo ~1 000 000 007~.

Ejemplo 1 de Entrada

3 
-1 2 -1

Ejemplo 1 de Salida

0

Ejemplo 2 de Entrada

3 
-1 -1 -1

Ejemplo 2 de Salida

2

Ejemplo 3 de Entrada

6 
-1 -1 -1 2 -1 -1

Ejemplo 3 de Salida

3