Su amiga Hange es una naturalista muy famosa y le dice que actualmente está tratando de contar el número de variedades de una especie de árboles muy particular que descubrió hace dos años.

Te dice que estos árboles son muy peculiares. Primero, son planos: uno de sus lados mira al sur y el otro al norte. En segundo lugar, cuando una de sus ramas se divide, se divide exactamente en dos subramas, que van en dos direcciones opuestas: una va hacia el oeste y la otra hacia el este. En general, tal árbol puede ser fácilmente representado como árbol binario como el que los científicos en computación están acostumbrados.

Como gran programador, te emocionas tan pronto como oyes hablar de árboles binarios. Hange continúa con sus explicaciones: en un árbol así, las ramas son horizontales o suben, nunca bajan.

Aún obsesionado por los árboles binarios, se da cuenta de que esto corresponde a decir que, en la representación del árbol binario, los nodos representan la division de una rama, y estan etiquetados por su altura en respecto al suelo. Entonces la etiqueta de un nodo no raiz es siempre mayor o igual que la etiqueta de su padre. Los árboles vacíos no están etiquetados. Si bien esta propiedad le parece bastante aburrida y no muy interesante, Hange continúa y le cuenta un hecho realmente sorprendente y sutil que descubrió recientemente acerca de sus especies de árboles favorita:

Cada árbol de un tipo dado, posee el mismo recorrido en orden de su arbol binario que todos los demas arboles de ese mismo tipo.(El recorrido en orden del árbol vacío es la secuencia vacía y, si un árbol no está vacío, su recorrido en orden es la concatenación del recorrido en orden del subárbol izquierdo, seguido de la etiqueta del nodo en el que se encuentra, seguido del recorrido en orden del subárbol derecho.)

Hange le pide que cree un programa que dado el recorrido en orden de un tipo de arbol, diga cuantos arboles diferentes pueden existir de ese tipo.

Calificación:

• ~5~ puntos: ~N\leq5~.
• ~10~ puntos: ~N\leq10~.
• ~15~ puntos: ~N\leq200~.
• ~40~ puntos: ~N\leq2000~.
• ~30~ puntos: ~N\leq1000000~.

Entrada:

La entrada consta de las siguientes líneas:

• En la primera línea: el número ~N~ de elementos de la secuencia de elevaciones producidas por el recorrido en orden de cualquier árbol de la especie.
• Las ~N~ líneas siguientes representan la secuencia de elevaciones, en milímetros, con un número entero por línea.

Tanto ~N~ como las elevaciones son mayores o iguales a ~0~ y menores o iguales a ~1 000 000~.

Salida:

Imprima un solo entero que represente la cantidad de arboles distintos de esa especie, módulo ~1000000007~.

Ejemplo de entrada 1:

6 
3 
1 
6 
2 
4 
5

Ejemplo de salida 1:

1

Ejemplo de entrada 2:

6 
1 
1 
1 
1 
1 
1

Ejemplo de salida 2:

132